Handbook of Combinatorial Optimization Supplement Volume A
Combinatorial (or discrete) optimization is one of the most active fields in the interface of operations research, computer science, and applied math ematics. Combinatorial optimization problems arise in various applications, including communications net
- PDF / 61,477,995 Bytes
- 650 Pages / 439.37 x 666.142 pts Page_size
- 80 Downloads / 201 Views
Handbook of Combinatorial Optimization Supplement Volume A
Edited by
Ding-Zhu Du Department of Computer Science. University of Minnesota. U.S.A. and Institute afApplied Mathematics, Academia Sillica. P. R. China
and
Panos M. Pardalos Department of Industrial and Systems Engineering, University of Florida, U.S.A .
.....
"
SPRINGER-SCIENCE+BUSINESS MEDIA, B.V.
A c.I.P. Catalogue record for this book is available from the Library of Congress.
ISBN 978-1-4419-4813-7 ISBN 978-1-4757-3023-4 (eBook) DOI 10.1007/978-1-4757-3023-4
Prin led 011
(/cid~fi'ee
papa
AII Rights Reservcd © 1999 Springer Science+Business Media Dordrecht Originally published by Kluwer Academic Publishers in 1999 Softcover reprint of the hardcover 1st edition 1999 No part of the material protected by this copyright notice may be reproduccd or utilized in any form or by any means. electronic or mechanical. including photocopying. recording ar by any information storage and retricval system, without written permission from the copyright owner.
Contents Preface ............................................................. vii The Maximum Clique Problem .................................... 1 Immanuel M. Bomze, Marco Budinich, Panos M. Pardalos, and Marcello Pelillo Linear Assignment Problems and Extensions ................... 75 Rainer E. Burkard and Eranda 9ela Bin Packing Approximation Algorithms: Combinatorial Analysis .......................................... 151 Edward G. Coffman, Gabor Galambos, Silvano Martello, and Daniele Vigo Feedback Set Problems .......................................... 209 Paola Festa, Panos M. Pardalos, and Mauricio G. C. Resende Neural Networks Approaches for Combinatorial Optimization Problems ............ Theodore B. Trafalis and Suat K asap cc
•••••••••••••••••••••••••••••
259
Frequency Assignment Problems ................................ 295 Robert A. Murphey, Panos M. Pardalos, Mauricio G. C. Resende Algorithms for the Satisfiability (SAT) Problem .............. 379 J1m Gu, Paul W. Purdom, John Franco, and Benjamin W. Wah The Steiner Ratio of Lp-planes .................................. 573 Jens Albrecht and Dietmar Cieslik A Cogitative Algorithm for Solving the Equal Circles Packing Problem ............................. 591 Wenqi Huang, Yu-Liang Wu, and C. K. Wong Author Index ..................................................... 607
VI
Contents
Subject Index ..................................................... 633
Vll
Preface
Combinatorial (or discrete) optimization is one of the most active fields in the interface of operations research, computer science, and applied mathematics. Combinatorial optimization problems arise in various applications, including communications network design, VLSI design, machine vision, airline crew scheduling, corporate planning, computer-aided design and manufacturing, database query design, cellular telephone frequency assignment, constraint directed reasoning, and computational biology. Furthermore, combinatorial optimization problems occur in many diver
