Efficient Approximation and Online Algorithms
In this book, we present some recent advances in the ?eld of combinatorial optimization focusing on the design of e?cient approximation and on-line - gorithms. Combinatorial optimization and polynomial time approximation are verycloselyrelated:givenanNP-hardcombinatorialoptimizationproblem,i. e., a problem for which no polynomial time algorithm exists unlessP =NP,one important approach used by computer scientists is to consider polynomial time algorithms that do not produce optimum solutions, but solutions that are pr- ably close to the optimum. A natural partition of combinatorial optimization problems into two classes is then of both practical and theoretical interest: the problemsthat arefully approximable, i. e., thoseforwhich thereis anapproxi- tion 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 ?xed 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 revealedduringtime. Inthiscase,knownastheon-linecase,thegoalistodesign algorithms that are able to produce solutions that are close to the best possible solution that can be produced by any o?-line algorithm, i. e., an algorithm that knows the input in advance. 1 Theseissueshavebeentreatedinsomerecenttexts ,butinthelastfewyears a huge amount of new results have been produced in the area of approximation and on-line algorithms.
Charts recent advances in the fieldContains carefully selected papers that cover some classical problems of scheduling, packing, and graph theoryContains new optimization problems arising in various applications like networks, data mining or classification