
Efficient Approximation and Online Algorithms
Recent Progress on Classical Combinatorial Optimization Problems and New Applications
Springer (Publisher)
Published on 6. February 2006
Book
Paperback/Softback
VIII, 348 pages
978-3-540-32212-2 (ISBN)
Description
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.
More details
Series
Edition
2006 ed.
Language
English
Place of publication
Berlin
Germany
Publishing group
Springer Berlin
Target group
Professional and scholarly
Research
Illustrations
VIII, 348 p.
Dimensions
Height: 23.5 cm
Width: 15.5 cm
Weight
557 gr
ISBN-13
978-3-540-32212-2 (9783540322122)
DOI
10.1007/11671541
Schweitzer Classification
Persons
Content
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.