Skip to main content
SpringerLink
Log in

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August, 21-23, 2009, Proceedings

  • Conference proceedings
  • © 2009

Overview

Editors:
  1. Irit Dinur

    1. Dept. of Applied Math and Computer Science, The Weizmann Institute of Science, Rehovot, Israel

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Klaus Jansen

    1. Institute for Computer Science and Applied Mathematics, University of Kiel, Kiel, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Joseph Naor

    1. Technion, Computer Science Department, Haifa, Israel

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. José Rolim

    1. University of Geneva, Centre Universitaire d’Informatique, Carouge, Switzerland

    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 5687)

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 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.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 (54 papers)

  1. Front Matter

    Download chapter PDF

  2. Contributed Talks of APPROX

    1. Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs

      • Ashkan Aazami, Joseph Cheriyan, Krishnam Raju Jampani
      Pages 1-14

    2. Adaptive Sampling for k-Means Clustering

      • Ankit Aggarwal, Amit Deshpande, Ravi Kannan
      Pages 15-28

    3. Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs

      • Douglas E. Carroll, Adam Meyerson, Brian Tagiku
      Pages 29-41

    4. Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs

      • Chandra Chekuri, Alina Ene, Nitish Korula
      Pages 42-55

    5. Truthful Mechanisms via Greedy Iterative Packing

      • Chandra Chekuri, Iftah Gamzu
      Pages 56-69

    6. Resource Minimization Job Scheduling

      • Julia Chuzhoy, Paolo Codenotti
      Pages 70-83

    7. The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders

      • José R. Correa, Martin Skutella, José Verschae
      Pages 84-97

    8. New Hardness Results for Diophantine Approximation

      • Friedrich Eisenbrand, Thomas Rothvoß
      Pages 98-110

    9. PASS Approximation

      • Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh
      Pages 111-124

    10. Optimal Sherali-Adams Gaps from Pairwise Independence

      • Konstantinos Georgiou, Avner Magen, Madhur Tulsiani
      Pages 125-139

    11. An Approximation Scheme for Terrain Guarding

      • Matt Gibson, Gaurav Kanade, Erik Krohn, Kasturi Varadarajan
      Pages 140-148

    12. Scheduling with Outliers

      • Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Danny Segev
      Pages 149-162

    13. Improved Inapproximability Results for Maximum k-Colorable Subgraph

      • Venkatesan Guruswami, Ali Kemal Sinop
      Pages 163-176

    14. Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems

      • Rolf Harren, Rob van Stee
      Pages 177-189

    15. On the Optimality of Gluing over Scales

      • Alex Jaffe, James R. Lee, Mohammad Moharrami
      Pages 190-201

    16. On Hardness of Pricing Items for Single-Minded Bidders

      • Rohit Khandekar, Tracy Kimbrel, Konstantin Makarychev, Maxim Sviridenko
      Pages 202-216

    17. Real-Time Message Routing and Scheduling

      • Ronald Koch, Britta Peis, Martin Skutella, Andreas Wiese
      Pages 217-230

    18. Approximating Some Network Design Problems with Node Costs

      • Guy Kortsarz, Zeev Nutov
      Pages 231-243

    19. Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

      • Jon Lee, Maxim Sviridenko, Jan Vondrák
      Pages 244-257
Back to top

Other volumes

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

Keywords

Editors and Affiliations

  • Dept. of Applied Math and Computer Science, The Weizmann Institute of Science, Rehovot, Israel

    Irit Dinur

  • Institute for Computer Science and Applied Mathematics, University of Kiel, Kiel, Germany

    Klaus Jansen

  • Technion, Computer Science Department, Haifa, Israel

    Joseph Naor

  • University of Geneva, Centre Universitaire d’Informatique, Carouge, Switzerland

    José Rolim

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation