Efficient Approximation And Online Algorithms

by Bampis, Evripidis; Jansen, Klaus; Kenyon, Claire

• ISBN13: 9783540322122
• ISBN10: 3540322124
• Format: Paperback
• Copyright: 2006-03-15
• Publisher: Springer-Verlag New York Inc

Summary

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

Contributed Talks
On Approximation Algorithms for Data Mining Applications
Foto N. Afrati	1	(29)
A Survey of Approximation Results for Local Search Algorithms
Eric Angel	30	(44)
Approximation Algorithms for Path Coloring in Trees
Ioannis Caragiannis, Christos Kaklamanis, Giuseppe Persiano	74	(23)
Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow
Thomas Erlebach	97	(38)
Independence and Coloring Problems on Intersection Graphs of Disks
Thomas Erlebach, Jiri Fiala	135	(21)
Approximation Algorithms for Min-Max and Max-Min Resource Sharing Problems, and Applications
Klaus Jansen	156	(47)
A Simpler Proof of Preemptive Total Flow Time Approximation on Parallel Machines
Stefano Leonardi	203	(10)
Approximating a Class of Classification Problems
Ioannis Milis	213	(37)
List Scheduling in Order of a-Points on a Single Machine
Martin Skutella	250	(42)
Approximation Algorithms for the k-Median Problem
Roberto Solis-Oba	292	(29)
The Lovász-Local-Lemma and Scheduling
Anand Srivastav	321	(28)
Author Index	349