Efficient Approximation and Online Algorithms: Recent Progress on Classical Combinatorial Optimization Problems and New Applications (Lecture Notes in Computer Science)

Bampis, Evripidis (Editor)/ Jansen, Klaus (Editor)/ Kenyon, Claire (Editor)

ISBN 10: 3540322124 / ISBN 13: 9783540322122

Editore: Springer-Verlag New York Inc, 2006

Riguardo questo articolo

1st edition. 349 pages. 9.25x6.25x0.75 inches. In Stock. Codice articolo x-3540322124

Dati bibliografici

Titolo: Efficient Approximation and Online ...

Casa editrice: Springer-Verlag New York Inc

Data di pubblicazione: 2006

Legatura: Paperback

Condizione: Brand New

Descrizione articolo

Riassunto:

This book provides a good opportunity for computer science practitioners and researchers to get in sync with 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.

Contenuti:

Contributed Talks.- On Approximation Algorithms for Data Mining Applications.- A Survey of Approximation Results for Local Search Algorithms.- Approximation Algorithms for Path Coloring in Trees.- Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow.- Independence and Coloring Problems on Intersection Graphs of Disks.- Approximation Algorithms for Min-Max and Max-Min Resource Sharing Problems, and Applications.- A Simpler Proof of Preemptive Total Flow Time Approximation on Parallel Machines.- Approximating a Class of Classification Problems.- List Scheduling in Order of ?-Points on a Single Machine.- Approximation Algorithms for the k-Median Problem.- The Lovász-Local-Lemma and Scheduling.