Skip to main content
SpringerLink
Log in
Book cover

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

10th International Workshop, APPROX 2007, and 11th International Workshop, RANDOM 2007, Princeton, NJ, USA, August 20-22, 2007, Proceedings

  • Conference proceedings
  • © 2007

Overview

Editors:
  1. Moses Charikar

    1. Computer Science Dept., Princeton University, Princeton, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Klaus Jansen

    1. Institut für Informatik, Christian-Albrechts-Universität zu Kiel,, Kiel, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Omer Reingold

    1. Faculty of Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, Israel

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. José D. P. Rolim

    1. Centre Universitaire d’Informatique,, Geneva, 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 4627)

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 (44 papers)

  1. Front Matter

    Download chapter PDF

  2. Contributed Talks of APPROX

    1. Approximation Algorithms and Hardness for Domination with Propagation

      • Ashkan Aazami, Michael D. Stilp
      Pages 1-15

    2. A Knapsack Secretary Problem with Applications

      • Moshe Babaioff, Nicole Immorlica, David Kempe, Robert Kleinberg
      Pages 16-28

    3. An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

      • Jaroslaw Byrka
      Pages 29-43

    4. Improved Approximation Algorithms for the Spanning Star Forest Problem

      • Ning Chen, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra, Gyanit Singh
      Pages 44-58

    5. Packing and Covering δ-Hyperbolic Spaces by Balls

      • Victor Chepoi, Bertrand Estellon
      Pages 59-73

    6. Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems

      • Ilias Diakonikolas, Mihalis Yannakakis
      Pages 74-88

    7. Two Randomized Mechanisms for Combinatorial Auctions

      • Shahar Dobzinski
      Pages 89-103

    8. Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs

      • Uriel Feige, Mohit Singh
      Pages 104-118

    9. Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems with Unit-Time Windows

      • Greg N. Frederickson, Barry Wittman
      Pages 119-133

    10. Stochastic Steiner Tree with Non-uniform Inflation

      • Anupam Gupta, MohammadTaghi Hajiaghayi, Amit Kumar
      Pages 134-148

    11. On the Approximation Resistance of a Random Predicate

      • Johan Håstad
      Pages 149-163

    12. Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to ℓ1 Embeddability of Negative Type Metrics

      • Hamed Hatami, Avner Magen, Evangelos Markakis
      Pages 164-179

    13. Optimal Resource Augmentations for Online Knapsack

      • Kazuo Iwama, Guochuan Zhang
      Pages 180-188

    14. Soft Edge Coloring

      • Chadi Kari, Yoo-Ah Kim, Seungjoon Lee, Alexander Russell, Minho Shin
      Pages 189-203

    15. Approximation Algorithms for the Max-Min Allocation Problem

      • Subhash Khot, Ashok Kumar Ponnuswami
      Pages 204-217

    16. Hardness of Embedding Metric Spaces of Equal Size

      • Subhash Khot, Rishi Saket
      Pages 218-227

    17. Coarse Differentiation and Multi-flows in Planar Graphs

      • James R. Lee, Prasad Raghavendra
      Pages 228-241

    18. Maximum Gradient Embeddings and Monotone Clustering

      • Manor Mendel, Assaf Naor
      Pages 242-256

    19. Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems

      • Viswanath Nagarajan, R. Ravi
      Pages 257-270
Back to top

Other volumes

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

Keywords

Editors and Affiliations

  • Computer Science Dept., Princeton University, Princeton, USA

    Moses Charikar

  • Institut für Informatik, Christian-Albrechts-Universität zu Kiel,, Kiel, Germany

    Klaus Jansen

  • Faculty of Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, Israel

    Omer Reingold

  • Centre Universitaire d’Informatique,, Geneva, Switzerland

    José D. P. Rolim

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation