| This book provides a good opportunity for computer science practitioners and researchers to get in sync with the current state-of-the-art and future trends in the field of combinatorial optimization and online algorithms. Recent advances in this area are presented focusing on the design of efficient approximation and on-line algorithms. One central idea in the book is to use a linear program relaxation of the problem, randomization and rounding techniques. This state-of-the-art survey contains 11 carefully selected papers that cover some classical problems of scheduling, of packing, and of graph theory, but also new optimization problems arising in various applications like networks, data mining or classification.
In this book, we present some recent advances in the field of combinatorial optimization focusing on the design of efficient approximation and on-line algorithms. Combinatorial optimization and polynomial time approximation are very closely related: given an NP-hard combinatorial optimization problem, i.e., a problem for which no polynomial time algorithm exists unless P = NP, one important approach used by computer scientists is to consider polynomial time algorithms that do not produce optimum solutions, but solutions that are provably close to the optimum. A natural partition of combinatorial optimization problems into two classes is then of both practical and theoretical interest: the problems that are fully approximable, i.e., those for which there is an approximation algorithm that can approach the optimum with any arbitrary precision in terms of relative error and the problems that are partly approximable, i.e., those for which it is possible to approach the optimum only until a fixed factor unless P = NP. For some of these problems, especially those that are motivated by practical applications, the input may not be completely known in advance, but revealed during time. In this case, known as the on-line case, the goal is to design algorithms that are able to produce solutions that are close to the best possible solution that can be produced by any off-line algorithm, i.e., an algorithm that knows the input in advance.
These issues have been treated in some recent texts, but in the last few years a huge amount of new results have been produced in the area of approximation and on-line algorithms. This book is devoted to the study of some classical problems of scheduling, of packing, and of graph theory, but also new optimization problems arising in various applications such as networks, data mining or classification. One central idea in the book is to use a linear program relaxation of the problem, randomization and rounding techniques. |
