Efficient Approximation and Online Algorithms: Recent Progress on Classical Combinatorial Optimization Problems and New Applications

Foto N. Afrati (auth.), Evripidis Bampis, Klaus Jansen, Claire Kenyon (eds.)3540322124, 9783540322122

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.

---

Table of contents :
Front Matter….Pages –
On Approximation Algorithms for Data Mining Applications….Pages 1-29
A Survey of Approximation Results for Local Search Algorithms….Pages 30-73
Approximation Algorithms for Path Coloring in Trees….Pages 74-96
Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow….Pages 97-134
Independence and Coloring Problems on Intersection Graphs of Disks….Pages 135-155
Approximation Algorithms for Min-Max and Max-Min Resource Sharing Problems, and Applications….Pages 156-202
A Simpler Proof of Preemptive Total Flow Time Approximation on Parallel Machines….Pages 203-212
Approximating a Class of Classification Problems….Pages 213-249
List Scheduling in Order of α -Points on a Single Machine….Pages 250-291
Approximation Algorithms for the k -Median Problem….Pages 292-320
The Lovász-Local-Lemma and Scheduling….Pages 321-347
Back Matter….Pages –