Skip to main content
SpringerLink
Log in
Book cover
  • Conference proceedings
  • © 2006

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

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)

Conference series link(s): APPROX: International Workshop on Approximation Algorithms for Combinatorial Optimization, RANDOM: International Workshop on Randomization and Approximation Techniques in Computer Science

Conference proceedings info: APPROX 2006, RANDOM 2006.

Sections

Buy it now

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

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

Table of contents (46 papers)

  1. Front Matter

    PDF

  2. Invited Talks

    1. On Nontrivial Approximation of CSPs

      • Johan Håstad
      Pages 1-1

  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

    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

    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

    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
Back to top

Other Volumes

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

Back to top

Keywords

Back to top

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

Back to top

Bibliographic Information

Back to top

Publish with us

Policies and ethics

Back to top
Access via your institution

Buy it now

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

Search

Navigation