Handbook of Combinatorial Optimization Supplement Volume B
This is a supplementary volume to the major three-volume Handbook of Combinatorial Optimization set, as well as the Supplement Volume A. It can also be regarded as a stand-alone volume which presents chapters dealing with various aspects of the
- PDF / 13,793,898 Bytes
- 395 Pages / 432 x 648 pts Page_size
- 31 Downloads / 249 Views
HANDBOOK OF COMBINATORIAL OPTIMIZATION Supplement Volume B
Edited by DING-ZHU DU University of Minnesota, Minneapolis, MN PANOS M. PARDALOS University of Florida, Gainesville, FL
Springer
eBook ISBN: Print ISBN:
0-387-23830-1 0-387-23829-8
©2005 Springer Science + Business Media, Inc. Print ©2005 Springer Science + Business Media, Inc. Boston All rights reserved No part of this eBook may be reproduced or transmitted in any form or by any means, electronic, mechanical, recording, or otherwise, without written consent from the Publisher Created in the United States of America
Visit Springer's eBookstore at: and the Springer Global Website Online at:
http://ebooks.springerlink.com http://www.springeronline.com
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 diverse areas such as linear and integer programming, graph theory, artificial intelligence, and number theory. All these problems, when formulated mathematically as the minimization or maximization of a certain function defined on some domain, have a commonality of discreteness. Historically, combinatorial optimization starts with linear programming. Linear programming has an entire range of important applications including production planning and distribution, personnel assignment, finance, allocation of economic resources, circuit simulation, and control systems. Leonid Kantorovich and Tjalling Koopmans received the Nobel Prize (1975) for their work on the optimal allocation of resources. Two important discoveries, the ellipsoid method (1979) and interior point approaches (1984) both provide polynomial time algorithms for linear programming. These algorithms have had a profound effect in combinatorial optimization. Many polynomial-time solvable combinatorial optimization problems are special cases of linear programming (e.g. matching and maximum flow). In addition, linear programming relaxations are often the basis for many approximation algorithms for solving NP-hard problems (e.g. dual heuristics). Two other developments with a great effect on combinatorial optimization are the design of efficient integer programming software and the availability of parallel computers. In the last decade, the use of integer programming models has changed and increased dramatically. Two decades ago, only problems with up to 100 integer variables could be solved in a computer. Today we can solve problems to optimality with thousands of integer variables. Furthermore, we can compute provably good approximate solutions to problems with millions of integ
Data Loading...
