This updated and revised 2nd edition of the three-volume Combinatorial Optimization series covers a very large set of topics in this area, dealing with fundamental notions and approaches as well as several classical applications of Combinatorial Optimization.
Combinatorial Optimization is a multidisciplinary field, lying at the interface of three major scientific domains: applied mathematics, theoretical computer science, and management studies. Its focus is on finding the least-cost solution to a mathematical problem in which each solution is associated with a numerical cost. In many such problems, exhaustive search is not feasible, so the approach taken is to operate within the domain of optimization problems, in which the set of feasible solutions is discrete or can be reduced to discrete, and in which the goal is to find the best solution. Some common problems involving combinatorial optimization are the traveling salesman problem and the minimum spanning tree problem.
Combinatorial Optimization is a subset of optimization that is related to operations research, algorithm theory, and computational complexity theory. It has important applications in several fields, including artificial intelligence, mathematics, and software engineering.
This second volume, which addresses the various paradigms and approaches taken in Combinatorial Optimization, is divided into two parts:
– Paradigmatic Problems, which discusses several famous combinatorial optimization problems, such as max cut, min coloring, optimal satisfiability TSP, etc., the study of which has largely contributed to the development, the legitimization and the establishment of Combinatorial Optimization as one of the most active current scientific domains.
– New Approaches, which presents the methodological approaches that fertilize and are fertilized by Combinatorial Optimization such as polynomial approximation, on-line computation, robustness, etc., and, more recently, algorithmic game theory.
The three volumes of this series form a coherent whole. The set of books is intended to be a self-contained treatment requiring only basic understanding and knowledge of a few mathematical theories and concepts. It is intended for researchers, practitioners and MSc or PhD students.