Hybrid heuristics for minimum cardinality set covering problems

Minimum cardinality set covering problems (MCSCP) tend to be more difficult to solve than weighted set covering problems because the cost or weight associated with each variable is the same. Since MCSCP is NP-complete, large problem instances are commonly solved using some form of a greedy heuristic. In this paper hybrid algorithms are developed and tested against two common forms of the greedy heuristic. Although all the algorithms tested have the same worst case bounds provided by Ho [7], empirical results for 60 large randomly generated problems indicate that one algorithm performed better than the others.     

Book reviews

Soviet Nuclear Strategy from Stalin to Gorbachev: a Revolution in Soviet Military and Political Thinking. By Honore M. Catudal. Mansell, London (1988), ISBN 0–7201–2000–4, £25.00

The Military: More Than Just a Job? Edited by Charles C. Moskos and Frank R. Wood. Pergamon‐Brassey's, London (1988), ISBN 0–08–034321‐X, £17.00 ($30.00)

Douglas Haig, 1861–1928. By Gerard J. de Groot. Unwin Hyman, London (1988), ISBN 004 4401922, £20.00

Defence Policy Making. A Comparative Analysis. Edited by G. M. Dillon. Leicester University Press, Leicester (1988), ISBN 0–715–1268–5, £10.95

The Future of U.K. Air Power. Edited by P. Sabin. Brassey's, London (1988), ISBN 0–08–035825‐X (hardcover), 0–08–036256–7 (flexicover), hardcover £18.95 ($34.00), flexicover £9.95 ($17.95)     

Book reviews

Small Wars Manual. United States Marine Corps 1940, with introduction by Ronald Schaffer, Sunflower University Press, Manhattan, Kansas, (1990), ISBN: 0-89745-112-0.

Military Mindlessness: an Informal Compendium. Edited by Raymond Horricks. Transaction Publishers, New Brunswick and London, (1993), ISBN: 1-56000-105-4. Price $26.95

Sipri Yearbook 1993: World Armaments and Disarmament, Oxford University Press, Oxford, (1993) ISBN 0-19-829166-3 - Price £50.00

Nigeria: The Politics of Adjustment and Democracy. By Julius O. Ihonvbere. Transaction Publishers, London & New Brunswick (1994), ISBN 1-56000-093-7, Price £34.95     

Rectilinear m-Center problem

In this article we consider the unweighted m-center problem with rectilinear distance. We preent an O(n^m–2 log n) algorithm for the m-center problem where m ≥ 4.     

Book Reviews

Strategic Geography. By Hugh Faringdon. Routledge, London (1989), ISBN 0-415-00980-4, £40.00

Field Artillery and Firepower. By J. B. A. Bailey. The Military Press, Oxford (1989), ISBN 0-85066-810-7, £25.00 (hardback), ISBN 0-85066-811-5, £14.50 (paperback)

U.S.-Soviet Security Cooperation. Edited by Alexander L. George, Philip J. Farley and Alexander Dallin. Oxford University Press, New York (1988), ISBN 0-19-505397-4, £30.00 (hardback), $19.95 (paperback)

Non-production by Industry of Chemical-warfare Agents: Technical Verification under a Chemical Weapons Convention. Edited by S. J. Lundin. SIPRI/Oxford University Press, Oxford (1988), ISBN 0-19-829129-9, £19.50

Ireland's Terrorist Trauma: Interdisciplinary Perspectives. Edited by Alan O'Day and Yonah Alexander. Harvester Wheatsheaf, Hemel Hempstead (1989), ISBN 7450-049003, £27.50 ($48.65)

Pilots and Rebels: the Use of Aircraft in Unconventional Warfare 1918-1988. By P. A. Towle. Brassey's (UK), London (1989), ISBN 0-08-036712-7, £29.95 ($53.95)