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

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

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)

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 2011, RANDOM 2011.

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

  1. Front Matter

    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

    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

    14. Periodicity and Cyclic Shifts via Linear Sketches

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

    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

Back to top

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

Keywords

Back to top

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

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