Efficient approximation and online algorithms : recent progress on classical combinatorial optimization problems and new applications

Bibliographic Information

Efficient approximation and online algorithms : recent progress on classical combinatorial optimization problems and new applications

Evripidis Bampis, Klaus Jansen, Claire Kenyon (eds.)

(Lecture notes in computer science, 3484)

Springer, c2006

Search this Book/Journal
Note

Includes bibliographical references and index

"State-of-the-art survey"--On Cover

Description and Table of Contents

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.

Table of Contents

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 Lovasz-Local-Lemma and Scheduling.

by "Nielsen BookData"

Related Books: 1-1 of 1
Details
  • NCID
    BA75871634
  • ISBN
    • 3540322124
  • LCCN
    2006920093
  • Country Code
    gw
  • Title Language Code
    eng
  • Text Language Code
    eng
  • Place of Publication
    Berlin
  • Pages/Volumes
    vi, 347 p.
  • Size
    24 cm
  • Classification
  • Parent Bibliography ID
Page Top