Skip to main content
SpringerLink
Log in

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings

  • Conference proceedings
  • © 2010

Overview

Editors:
  1. Maria Serna

    1. Universitat Politecnica de Catalunya, Departament de Llenguatges i Sistemes Informatics, Campus Nord - Ed Omega, Barcelona, Spain

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Ronen Shaltiel

    1. Department of Computer Science, University of Haifa, Haifa, Israel

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Klaus Jansen

    1. Department of Computer Science, University of Kiel, Kiel, Germany

    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

  • Unique visibility
  • State-of-the-art survey
  • Fast-track conference proceedings

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

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

  1. Front Matter

    Download chapter PDF

  2. Contributed Talks of APPROX

    1. Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem

      • Hyung-Chan An, Robert D. Kleinberg, David B. Shmoys
      Pages 1-11

    2. Improved Inapproximability for Submodular Maximization

      • Per Austrin
      Pages 12-24

    3. Approximation Algorithms for the Directed k-Tour and k-Stroll Problems

      • MohammadHossein Bateni, Julia Chuzhoy
      Pages 25-38

    4. Submodular Secretary Problem and Extensions

      • MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Morteza Zadimoghaddam
      Pages 39-52

    5. Approximation Algorithms for Min-Max Generalization Problems

      • Piotr Berman, Sofya Raskhodnikova
      Pages 53-66

    6. Min-Power Strong Connectivity

      • Gruia Calinescu
      Pages 67-80

    7. The Complexity of Approximately Counting Stable Matchings

      • Prasad Chebolu, Leslie Ann Goldberg, Russell Martin
      Pages 81-94

    8. Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs

      • Victor Chepoi, Feodor F. Dragan, Ilan Newman, Yuri Rabinovich, Yann Vaxès
      Pages 95-109

    9. Approximating Linear Threshold Predicates

      • Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson
      Pages 110-123

    10. Approximating Sparsest Cut in Graphs of Bounded Treewidth

      • Eden Chlamtac, Robert Krauthgamer, Prasad Raghavendra
      Pages 124-137

    11. On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors

      • Irit Dinur, Igor Shinkar
      Pages 138-151

    12. Vertex Sparsifiers: New Results from Old Techniques

      • Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, Kunal Talwar
      Pages 152-165

    13. PTAS for Weighted Set Cover on Unit Squares

      • Thomas Erlebach, Erik Jan van Leeuwen
      Pages 166-177

    14. Improved Lower Bounds for the Universal and a priori TSP

      • Igor Gorodezky, Robert D. Kleinberg, David B. Shmoys, Gwen Spencer
      Pages 178-191

    15. Proximity Algorithms for Nearly-Doubling Spaces

      • Lee-Ad Gottlieb, Robert Krauthgamer
      Pages 192-204

    16. Matrix Sparsification and the Sparse Null Space Problem

      • Lee-Ad Gottlieb, Tyler Neylon
      Pages 205-218

    17. The Checkpoint Problem

      • MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Julián Mestre
      Pages 219-231

    18. The Euclidean Distortion of Flat Tori

      • Ishay Haviv, Oded Regev
      Pages 232-245

    19. Online Embeddings

      • Piotr Indyk, Avner Magen, Anastasios Sidiropoulos, Anastasios Zouzias
      Pages 246-259
Back to top

Other volumes

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

Keywords

Editors and Affiliations

  • Universitat Politecnica de Catalunya, Departament de Llenguatges i Sistemes Informatics, Campus Nord - Ed Omega, Barcelona, Spain

    Maria Serna

  • Department of Computer Science, University of Haifa, Haifa, Israel

    Ronen Shaltiel

  • Department of Computer Science, University of Kiel, Kiel, Germany

    Klaus Jansen

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

    José Rolim

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation