Skip to main content
SpringerLink
Log in
Book cover

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011, Proceedings

  • Conference proceedings
  • © 2011

Overview

Editors:
  1. Leslie Ann Goldberg

    1. Department of Computer Science, University of Liverpool, Liverpool, UK

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. 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

  3. R. Ravi

    1. Tepper School of Business, Carnegie Mellon University, Pittsburgh, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. José D. P. Rolim

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Fast-track conference proceedings
  • State-of-the-art research
  • Up-to-date results

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

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

  1. Front Matter

    Download chapter PDF

  2. Contributed Talks of APPROX

    1. New Tools for Graph Coloring

      • Sanjeev Arora, Rong Ge
      Pages 1-12

    2. Inapproximability of NP-Complete Variants of Nash Equilibrium

      • Per Austrin, Mark Braverman, Eden Chlamtáč
      Pages 13-25

    3. Sparse Recovery with Partial Support Knowledge

      • Khanh Do Ba, Piotr Indyk
      Pages 26-37

    4. On Capacitated Set Cover Problems

      • Nikhil Bansal, Ravishankar Krishnaswamy, Barna Saha
      Pages 38-49

    5. Bandwidth and Low Dimensional Embedding

      • Yair Bartal, Douglas E. Carroll, Adam Meyerson, Ofer Neiman
      Pages 50-61

    6. O(1)-Approximations for Maximum Movement Problems

      • Piotr Berman, Erik D. Demaine, Morteza Zadimoghaddam
      Pages 62-74

    7. Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs

      • Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna
      Pages 75-86

    8. Social Welfare in One-Sided Matching Markets without Money

      • Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna
      Pages 87-98

    9. Primal-Dual Schema and Lagrangian Relaxation for the k-Location-Routing Problem

      • Tim Carnes, David B. Shmoys
      Pages 99-110

    10. Scheduling Resources for Throughput Maximization

      • Venkatesan T. Chakaravarthy, Amit Kumar, Vinayaka Pandit, Sambuddha Roy, Yogish Sabharwal
      Pages 111-122

    11. Coloring and Maximum Independent Set of Rectangles

      • Parinya Chalermsook
      Pages 123-134

    12. A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems

      • Maurice Cheung, David B. Shmoys
      Pages 135-146

    13. A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius

      • Nachshon Cohen, Zeev Nutov
      Pages 147-157

    14. Periodicity and Cyclic Shifts via Linear Sketches

      • Michael S. Crouch, Andrew McGregor
      Pages 158-170

    15. An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs

      • Feodor F. Dragan, Ekkehard Köhler
      Pages 171-183

    16. Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle

      • Chandan Dubey, Thomas Holenstein
      Pages 184-193

    17. Opaque Sets

      • Adrian Dumitrescu, Minghui Jiang, János Pach
      Pages 194-205

    18. Exploring and Triangulating a Region by a Swarm of Robots

      • Sándor P. Fekete, Tom Kamphans, Alexander Kröller, Joseph S. B. Mitchell, Christiane Schmidt
      Pages 206-217

    19. Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract)

      • Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz
      Pages 218-229
Back to top

Other volumes

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

Keywords

About this book

This book constitutes the joint refereed proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2011, and the 15th International Workshop on Randomization and Computation, RANDOM 2011, held in Princeton, New Jersey, USA, in August 2011. The volume presents 29 revised full papers of the APPROX 2011 workshop, selected from 66 submissions, and 29 revised full papers of the RANDOM 2011 workshop, selected from 64 submissions. They were carefully reviewed and selected for inclusion in the book. In addition two abstracts of invited talks are included. APPROX focuses on algorithmic and complexity issues surrounding the development of efficient approximate solutions to computationally difficult problems. RANDOM is concerned with applications of randomness to computational and combinatorial problems.

Editors and Affiliations

  • Department of Computer Science, University of Liverpool, Liverpool, UK

    Leslie Ann Goldberg

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

    Klaus Jansen

  • Tepper School of Business, Carnegie Mellon University, Pittsburgh, USA

    R. Ravi

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

    José D. P. Rolim

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation