Skip to main content
SpringerLink
Log in
SpringerLink
Log in

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012, Proceedings

  • Conference proceedings
  • © 2012

Overview

Editors:
  1. Anupam Gupta

    1. Department of Computer Science, Carnegie Mellon University, Pittsburgh, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Klaus Jansen

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. José 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

  4. Rocco Servedio

    1. Department of Computer Science, Foundation School of Engineering and Applied Science, Columbia University, New York, USA

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

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

  1. Front Matter

    Download chapter PDF

  2. Contributed Talks of APPROX

    1. A New Point of NP-Hardness for 2-to-1 Label Cover

      • Per Austrin, Ryan O’Donnell, John Wright
      Pages 1-12

    2. Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems

      • Per Austrin, Toniann Pitassi, Yu Wu
      Pages 13-24

    3. Additive Approximation for Near-Perfect Phylogeny Construction

      • Pranjal Awasthi, Avrim Blum, Jamie Morgenstern, Or Sheffet
      Pages 25-36

    4. Improved Spectral-Norm Bounds for Clustering

      • Pranjal Awasthi, Or Sheffet
      Pages 37-49

    5. Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs

      • Piotr Berman, Grigory Yaroslavtsev
      Pages 50-60

    6. What’s the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid

      • Petros Boufounos, Volkan Cevher, Anna C. Gilbert, Yi Li, Martin J. Strauss
      Pages 61-72

    7. Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply

      • Parinya Chalermsook, Julia Chuzhoy, Sampath Kannan, Sanjeev Khanna
      Pages 73-84

    8. Online Flow Time Scheduling in the Presence of Preemption Overhead

      • Ho-Leung Chan, Tak-Wah Lam, Rongbin Li
      Pages 85-97

    9. Prize-Collecting Survivable Network Design in Node-Weighted Graphs

      • Chandra Chekuri, Alina Ene, Ali Vakilian
      Pages 98-109

    10. Approximating Minimum-Cost Connected T-Joins

      • Joseph Cheriyan, Zachary Friggstad, Zhihan Gao
      Pages 110-121

    11. iBGP and Constrained Connectivity

      • Michael Dinitz, Gordon Wilfong
      Pages 122-133

    12. Online Scheduling of Jobs with Fixed Start Times on Related Machines

      • Leah Epstein, Łukasz Jeż, Jiří Sgall, Rob van Stee
      Pages 134-145

    13. A Systematic Approach to Bound Factor Revealing LPs and Its Application to the Metric and Squared Metric Facility Location Problems

      • Cristina G. Fernandes, Luís A. A. Meira, Flávio K. Miyazawa, Lehilton L. C. Pedrosa
      Pages 146-157

    14. Approximating Bounded Occurrence Ordering CSPs

      • Venkatesan Guruswami, Yuan Zhou
      Pages 158-169

    15. On the NP-Hardness of Max-Not-2

      • Johan Håstad
      Pages 170-181

    16. The Remote Set Problem on Lattices

      • Ishay Haviv
      Pages 182-193

    17. Approximation Algorithms for Generalized and Variable-Sized Bin Covering

      • Matthias Hellwig, Alexander Souza
      Pages 194-205

    18. Approximating Minimum Linear Ordering Problems

      • Satoru Iwata, Prasad Tetali, Pushkar Tripathi
      Pages 206-217

    19. New Approximation Results for Resource Replication Problems

      • Samir Khuller, Barna Saha, Kanthi K. Sarpatwar
      Pages 218-230
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 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012, and the 16th International Workshop on Randomization and Computation, RANDOM 2012, held in Cambridge, Massachusetts, USA, in August 2011. The volume contains 28 contributed papers, selected by the APPROX Program Committee out of 70 submissions, and 28 contributed papers, selected by the RANDOM Program Committee out of 67 submissions. 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, Carnegie Mellon University, Pittsburgh, USA

    Anupam Gupta

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

    Klaus Jansen

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

    José Rolim

  • Department of Computer Science, Foundation School of Engineering and Applied Science, Columbia University, New York, USA

    Rocco Servedio

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation