Skip to main content
SpringerLink
Log in
Book cover

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013, Proceedings

  • Conference proceedings
  • © 2013

Overview

Editors:
  1. Prasad Raghavendra

    1. University of California, Berkeley, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Sofya Raskhodnikova

    1. Dept. of computer Science and Engineering, Pennsylvania State University, University Park, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Klaus Jansen

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. José D. P. 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

  • Conference Proceedings of the International Workshop on Approximation, Randomization, and Combinatorial Optimization

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

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

  1. Front Matter

    Download chapter PDF

  2. APPROX

    1. Spectral Sparsification in Dynamic Graph Streams

      • Kook Jin Ahn, Sudipto Guha, Andrew McGregor
      Pages 1-10

    2. The Online Stochastic Generalized Assignment Problem

      • Saeed Alaei, MohammadTaghi Hajiaghayi, Vahid Liaghat
      Pages 11-25

    3. On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems

      • Per Austrin, Rajsekar Manokaran, Cenny Wenner
      Pages 26-41

    4. Approximating Large Frequency Moments with Pick-and-Drop Sampling

      • Vladimir Braverman, Rafail Ostrovsky
      Pages 42-57

    5. Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams

      • Vladimir Braverman, Rafail Ostrovsky
      Pages 58-70

    6. Capacitated Network Design on Undirected Graphs

      • Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Shi Li, Srivatsan Narayanan
      Pages 71-80

    7. Scheduling Subset Tests: One-Time, Continuous, and How They Relate

      • Edith Cohen, Haim Kaplan, Yishay Mansour
      Pages 81-95

    8. On the Total Perimeter of Homothetic Convex Bodies in a Convex Container

      • Adrian Dumitrescu, Csaba D. Tóth
      Pages 96-109

    9. Partial Interval Set Cover – Trade-Offs between Scalability and Optimality

      • Katherine Edwards, Simon Griffiths, William Sean Kennedy
      Pages 110-125

    10. Online Square-into-Square Packing

      • Sándor P. Fekete, Hella-Franziska Hoffmann
      Pages 126-141

    11. Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions

      • Kyle Fox, Sungjin Im, Janardhan Kulkarni, Benjamin Moseley
      Pages 142-157

    12. Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems

      • Pierre Fraigniaud, Magnús M. Halldórsson, Boaz Patt-Shamir, Dror Rawitz, Adi Rosén
      Pages 158-172

    13. Multiple Traveling Salesmen in Asymmetric Metrics

      • Zachary Friggstad
      Pages 173-188

    14. Approximate Indexability and Bandit Problems with Concave Rewards and Delayed Feedback

      • Sudipto Guha, Kamesh Munagala
      Pages 189-204

    15. The Approximability of the Binary Paintshop Problem

      • Anupam Gupta, Satyen Kale, Viswanath Nagarajan, Rishi Saket, Baruch Schieber
      Pages 205-217

    16. Approximation Algorithms for Movement Repairmen

      • MohammadTaghi Hajiaghayi, Rohit Khandekar, M. Reza Khani, Guy Kortsarz
      Pages 218-232

    17. Improved Hardness of Approximating Chromatic Number

      • Sangxia Huang
      Pages 233-243

    18. A Pseudo-approximation for the Genus of Hamiltonian Graphs

      • Yury Makarychev, Amir Nayyeri, Anastasios Sidiropoulos
      Pages 244-259

    19. A Local Computation Approximation Scheme to Maximum Matching

      • Yishay Mansour, Shai Vardi
      Pages 260-273
Back to top

Other volumes

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

Keywords

About this book

This book constitutes the proceedings of the 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013, and the 17th International Workshop on Randomization and Computation, RANDOM 2013, held in August 2013 in the USA. The total of 48 carefully reviewed and selected papers presented in this volume consist of 23 APPROX papers selected out of 46 submissions, and 25 RANDOM papers selected out of 52 submissions. APPROX 2013 focuses on algorithmic and complexity theoretic issues relevant to the development of efficient approximate solutions to computationally difficult problems, while RANDOM 2013 focuses on applications of randomness to computational and combinatorial problems.

Editors and Affiliations

  • University of California, Berkeley, USA

    Prasad Raghavendra

  • Dept. of computer Science and Engineering, Pennsylvania State University, University Park, USA

    Sofya Raskhodnikova

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

    Klaus Jansen

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

    José D. P. Rolim

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation