Skip to main content
SpringerLink
Log in
Book cover

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30, 2006, Proceedings

  • Conference proceedings
  • © 2006

Overview

Editors:
  1. Josep Díaz

    1. Departament de Llenguatges i Sistemes Informatics, Universitat Politecnica de Catalunya, Barcelona

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Klaus Jansen

    1. Institute for Computer Science, University of Kiel, Kiel, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. José D. P. Rolim

    1. Centre Universitaire d’Informatique, Carouge, Switzerland

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Uri Zwick

    1. School of Computer Science, Tel Aviv University, Tel Aviv, Israel

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 4110)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (46 papers)

  1. Front Matter

    Download chapter PDF

  2. Invited Talks

    1. On Nontrivial Approximation of CSPs

      • Johan Håstad
      Pages 1-1

    2. Analysis of Algorithms on the Cores of Random Graphs

      • Nick Wormald
      Pages 2-2

  3. Contributed Talks of APPROX

    1. Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs

      • Christoph Ambühl, Thomas Erlebach, Matúš Mihalák, Marc Nunkesser
      Pages 3-14

    2. Approximating Precedence-Constrained Single Machine Scheduling by Coloring

      • Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson
      Pages 15-26

    3. Minimizing Setup and Beam-On Times in Radiation Therapy

      • Nikhil Bansal, Don Coppersmith, Baruch Schieber
      Pages 27-38

    4. On the Value of Preemption in Scheduling

      • Yair Bartal, Stefano Leonardi, Gil Shallom, Rene Sitters
      Pages 39-48

    5. An Improved Analysis for a Greedy Remote-Clique Algorithm Using Factor-Revealing LPs

      • Benjamin E. Birnbaum, Kenneth J. Goldman
      Pages 49-60

    6. Tight Results on Minimum Entropy Set Cover

      • Jean Cardinal, Samuel Fiorini, Gwenaël Joret
      Pages 61-69

    7. A Tight Lower Bound for the Steiner Point Removal Problem on Trees

      • T. -H. Hubert Chan, Donglin Xia, Goran Konjevod, Andrea Richa
      Pages 70-81

    8. Single-Source Stochastic Routing

      • Shuchi Chawla, Tim Roughgarden
      Pages 82-94

    9. An O(logn) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem

      • Chandra Chekuri, Martin Pál
      Pages 95-103

    10. Online Algorithms to Minimize Resource Reallocations and Network Communication

      • Sashka Davis, Jeff Edmonds, Russell Impagliazzo
      Pages 104-115

    11. Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs

      • Leah Epstein, Magnús M. Halldórsson, Asaf Levin, Hadas Shachnai
      Pages 116-127

    12. Combinatorial Algorithms for Data Migration to Minimize Average Completion Time

      • Rajiv Gandhi, Julián Mestre
      Pages 128-139

    13. LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times

      • Alexander Grigoriev, Maxim Sviridenko, Marc Uetz
      Pages 140-151

    14. Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees

      • M. T. Hajiaghayi, G. Kortsarz, M. R. Salavatipour
      Pages 152-163

    15. Improved Algorithms for Data Migration

      • Samir Khuller, Yoo-Ah Kim, Azarakhsh Malekian
      Pages 164-175

    16. Approximation Algorithms for Graph Homomorphism Problems

      • Michael Langberg, Yuval Rabani, Chaitanya Swamy
      Pages 176-187

    17. Improved Approximation Algorithm for the One-Warehouse Multi-Retailer Problem

      • Retsef Levi, Maxim Sviridenko
      Pages 188-199
Back to top

Other volumes

  1. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Keywords

Editors and Affiliations

  • Departament de Llenguatges i Sistemes Informatics, Universitat Politecnica de Catalunya, Barcelona

    Josep Díaz

  • Institute for Computer Science, University of Kiel, Kiel, Germany

    Klaus Jansen

  • Centre Universitaire d’Informatique, Carouge, Switzerland

    José D. P. Rolim

  • School of Computer Science, Tel Aviv University, Tel Aviv, Israel

    Uri Zwick

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation