Efficient Approximation and Online Algorithms

Recent Progress on Classical Combinatorial Optimization Problems and New Applications

Evripidis Bampis, Klaus Jansen, Claire Kenyon (Herausgeber)

Buch | Softcover

VIII, 348 Seiten

2006 | 2006
Springer Berlin (Verlag)
978-3-540-32212-2 (ISBN)

Artikel merken

lt;p>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.

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.

Erscheint lt. Verlag	6.2.2006
Reihe/Serie	Lecture Notes in Computer Science
Reihe/Serie	Theoretical Computer Science and General Issues
Zusatzinfo	VIII, 348 p.
Verlagsort	Berlin
Sprache	englisch
Maße	155 x 235 mm
Gewicht	547 g
Themenwelt	Informatik ► Theorie / Studium ► Algorithmen
Themenwelt	Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik
Schlagworte	algorithm • Algorithm analysis and problem complexity • Algorithmics • algorithms • Approximation • classification • combinatorial optimization • Complexity theory • Computational Complexity • Computational Discrete Mathematics • Computational Geometry • Computational Graph Theory • Computer • Computer Science • Data Mining • distributed algorithms • Graph Algorithms • Graph Drawing • local searching • network algorithms • On-line Algorithms • Optimization • Parallel Algorithms • Scheduling
ISBN-10	3-540-32212-4 / 3540322124
ISBN-13	978-3-540-32212-2 / 9783540322122
Zustand	Neuware