Non-Deterministic Polynomial Optimization Problems and Their Approximation
NP-problems are considered in this paper as recognition problems over some alphabet Σ, i.e. A ⊂ Σ* is is an NP problem if there exists a NDTM (non-deterministic Turing machine) recognizing A in polynomial time. It is easy to show that the following theore
- PDF / 14,700,519 Bytes
- 212 Pages / 481.899 x 691.66 pts Page_size
- 86 Downloads / 227 Views
e .
M
ANALYSIS AND DESIGN OF ALGORITHMS IN COMBINATORIAL OPTIMIZATION EDITED BY G. AUSIELLO AND M. LUCERTINI IASI - CNR ISTITUTO Dl AUTOMATICA UNIVERSIT A' Dl ROMA
SPRINGER-VERLAG WI EN GMBH
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concemed specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproduction by photocopying machine or similar means, and storage in data banks.
© 1981 by Springer-Verlag Wien Originally publisbed by Springer Verlag Wien- New York in 1981
ISBN 978-3-211-81626-4 DOI 10.1007/978-3-7091-2748-3
ISBN 978-3-7091-2748-3 (eBook)
PREFACE
The School in Analysis and Desi/{11 of Algorithms in Combinatorial Optimization was held in Udine in September 1979. It was financially supported by the National Research Council of Italy (CNR), by the International Center of Mechanical Sciences (CISM) and by the European Economic Community (CEE) and sponsored by GNASII-CNR, CSSCCA-CNR and lstituto di Automazione of the University of Rome. The organizers are pleased to express their thanks to the lecturers and participants who made the School stimulating and fruitful. Special thanks are addressed to the organizing committee and in particular to Angelo Marzollo, Alberto Marcbetti-Spaccamela and Paolo Serafini who provided their friendly and valuable help making the school successful.
G. Ausiello M. Lucertini
HTRODUCTION
The practical and theoretical relevance of problems to the NP-complete degree vf complexity are widely known. From the practical point of view it is sufficient to remember that in this class we find most of the combinatorial and optimization problems which b,,.·e the widest range of applications, for example scheduling problems, optimization problems on graphs, integer programming etc. As far as the theoretical relevance is concerned ;;.•e should remember that one of the most outstanding problems in Computer Science, the problem of deciding whether any NP-complete set can be recognized in polynomial time, coincides with the problem of knowing whether the computation power of a nondeterministic Turing machine which accepts a set in polynomial time is strictly stronger than the power of ordinary polynomially bounded Turing machines or not. Until recen#y the design of algorithms for finding exact approximate solutions to practical instances of hard combinatorial and optimization problems was the main concern of experts in Operations Research while the study of the complexity of these problems with respect to various computation models and the analysis of general solution techniques was the main interest of computer scientists. In 1978 at the Mathematisch Centrum in Amsterdam a conference was held on "Interfaces between Computer Science and Operations Research". In that occasion the experience and scientific interest of experts in mathematical programming and of Computer Scientists, interested in the design of algorithms and in the analysis of the complexity of problems, met a'!d fruitfully in
Data Loading...
