Skip to main content
SpringerLink
Log in

Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

8th International Workshop on Approximation Algorithms for Compinatorial Optimization Problems, APPROX 2005 and 9th International Workshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings

  • Conference proceedings
  • © 2005

Overview

Editors:
  1. Chandra Chekuri

    1. Dept. of Computer Science, University of Illinois, Urbana

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Klaus Jansen

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. José D. P. Rolim

    1. Battelle Bâtiment A, Centre Universitaire d’Informatique, Carouge, Geneva, Switzerland

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Luca Trevisan

    1. UC Berkeley,  

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

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

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

  1. Front Matter

    Download chapter PDF

  2. Contributed Talks of APPROX

    1. The Network as a Storage Device: Dynamic Routing with Bounded Buffers

      • Stanislav Angelov, Sanjeev Khanna, Keshav Kunal
      Pages 1-13

    2. Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT

      • Adi Avidor, Uri Zwick
      Pages 14-25

    3. What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs

      • Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, Kunal Talwar
      Pages 26-39

    4. A Rounding Algorithm for Approximating Minimum Manhattan Networks

      • Victor Chepoi, Karim Nouioua, Yann Vaxès
      Pages 40-51

    5. Packing Element-Disjoint Steiner Trees

      • Joseph Cheriyan, Mohammad R. Salavatipour
      Pages 52-61

    6. Approximating the Bandwidth of Caterpillars

      • Uriel Feige, Kunal Talwar
      Pages 62-73

    7. Where’s the Winner? Max-Finding and Sorting with Metric Costs

      • Anupam Gupta, Amit Kumar
      Pages 74-85

    8. What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization

      • Anupam Gupta, Martin Pál, Ramamoorthi Ravi, Amitabh Sinha
      Pages 86-98

    9. The Complexity of Making Unique Choices: Approximating 1-in-k SAT

      • Venkatesan Guruswami, Luca Trevisan
      Pages 99-110

    10. Approximating the Distortion

      • Alexander Hall, Christos Papadimitriou
      Pages 111-122

    11. Approximating the Best-Fit Tree Under L p Norms

      • Boulos Harb, Sampath Kannan, Andrew McGregor
      Pages 123-133

    12. Beating a Random Assignment

      • Gustav Hast
      Pages 134-145

    13. Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints

      • V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan
      Pages 146-157

    14. Approximation Algorithms for Network Design and Facility Location with Service Capacities

      • Jens Maßberg, Jens Vygen
      Pages 158-169

    15. Finding Graph Matchings in Data Streams

      • Andrew McGregor
      Pages 170-181

    16. A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses

      • Julián Mestre
      Pages 182-191

    17. Efficient Approximation of Convex Recolorings

      • Shlomo Moran, Sagi Snir
      Pages 192-208

    18. Approximation Algorithms for Requirement Cut on Graphs

      • Viswanath Nagarajan, Ramamoorthi Ravi
      Pages 209-220

    19. Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems

      • Jan Remy, Angelika Steger
      Pages 221-232
Back to top

Other volumes

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

Keywords

Editors and Affiliations

  • Dept. of Computer Science, University of Illinois, Urbana

    Chandra Chekuri

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

    Klaus Jansen

  • Battelle Bâtiment A, Centre Universitaire d’Informatique, Carouge, Geneva, Switzerland

    José D. P. Rolim

  • UC Berkeley,  

    Luca Trevisan

Bibliographic Information

  • Book Title: Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

  • Book Subtitle: 8th International Workshop on Approximation Algorithms for Compinatorial Optimization Problems, APPROX 2005 and 9th International Workshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings

  • Editors: Chandra Chekuri, Klaus Jansen, José D. P. Rolim, Luca Trevisan

  • Series Title: Lecture Notes in Computer Science

  • DOI: https://doi.org/10.1007/11538462

  • Publisher: Springer Berlin, Heidelberg

  • eBook Packages: Computer Science, Computer Science (R0)

  • Copyright Information: Springer-Verlag Berlin Heidelberg 2005

  • Softcover ISBN: 978-3-540-28239-6Published: 08 August 2005

  • eBook ISBN: 978-3-540-31874-3Published: 25 August 2005

  • Series ISSN: 0302-9743

  • Series E-ISSN: 1611-3349

  • Edition Number: 1

  • Number of Pages: XI, 495

  • Topics: Algorithm Analysis and Problem Complexity, Numeric Computing, Discrete Mathematics in Computer Science, Algorithms

Publish with us

Policies and ethics

Back to top

Search

Navigation