Skip to main content
SpringerLink
Log in

Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004 and 8th International Workshop on Randomization and Computation, RANDOM 2004, Cambridge, MA, USA August 22-24, 2004 , Proceedings

  • Conference proceedings
  • © 2004

Overview

Editors:
  1. 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

  2. Sanjeev Khanna

    1. Dept. of CIS, Univ. of Pennsylvania, Philadelphia

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. José D. P. Rolim

    1. Centre Universitaire d’Informatique, Carouge, Switzerland

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Dana Ron

    1. Tel-Aviv University, Ramat Aviv, Israel

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

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

  1. Front Matter

    Download chapter PDF

  2. Contributed Talks of APPROX

    1. Designing Networks with Existing Traffic to Support Fast Restoration

      • Mansoor Alicherry, Randeep Bhatia, Yung-Chun (Justin) Wan
      Pages 1-12

    2. Simultaneous Source Location

      • Konstantin Andreev, Charles Garrod, Bruce Maggs, Adam Meyerson
      Pages 13-26

    3. Computationally-Feasible Truthful Auctions for Convex Bundles

      • Moshe Babaioff, Liad Blumrosen
      Pages 27-38

    4. Randomized Approximation Algorithms for Set Multicover Problems with Applications to Reverse Engineering of Protein and Gene Networks

      • Piotr Berman, Bhaskar DasGupta, Eduardo Sontag
      Pages 39-50

    5. On the Crossing Spanning Tree Problem

      • Vittorio Bilò, Vineet Goyal, R. Ravi, Mohit Singh
      Pages 51-60

    6. A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One

      • Markus Bläser
      Pages 61-71

    7. Maximum Coverage Problem with Group Budget Constraints and Applications

      • Chandra Chekuri, Amit Kumar
      Pages 72-83

    8. The Greedy Algorithm for the Minimum Common String Partition Problem

      • Marek Chrobak, Petr Kolman, Jiří Sgall
      Pages 84-95

    9. Approximating Additive Distortion of Embeddings into Line Metrics

      • Kedar Dhamdhere
      Pages 96-104

    10. Polylogarithmic Inapproximability of the Radio Broadcast Problem

      • Michael Elkin, Guy Kortsarz
      Pages 105-116

    11. On Systems of Linear Equations with Two Variables per Equation

      • Uriel Feige, Daniel Reichman
      Pages 117-127

    12. An Auction-Based Market Equilibrium Algorithm for the Separable Gross Substitutability Case

      • Rahul Garg, Sanjiv Kapoor, Vijay Vazirani
      Pages 128-138

    13. Cost-Sharing Mechanisms for Network Design

      • Anupam Gupta, Aravind Srinivasan, Éva Tardos
      Pages 139-150

    14. Approximating Max k CSP Using Random Restrictions

      • Gustav Hast
      Pages 151-162

    15. Approximation Schemes for Broadcasting in Heterogenous Networks

      • Samir Khuller, Yoo-Ah Kim, Gerhard Woeginger
      Pages 163-170

    16. Centralized Deterministic Broadcasting in Undirected Multi-hop Radio Networks

      • Dariusz R. Kowalski, Andrzej Pelc
      Pages 171-182

    17. Convergence Issues in Competitive Games

      • Vahab S. Mirrokni, Adrian Vetta
      Pages 183-194

    18. Cuts and Orderings: On Semidefinite Relaxations for the Linear Ordering Problem

      • Alantha Newman
      Pages 195-206

    19. Min-Max Multiway Cut

      • Zoya Svitkina, Éva Tardos
      Pages 207-218
Back to top

Other volumes

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

Keywords

Editors and Affiliations

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

    Klaus Jansen

  • Dept. of CIS, Univ. of Pennsylvania, Philadelphia

    Sanjeev Khanna

  • Centre Universitaire d’Informatique, Carouge, Switzerland

    José D. P. Rolim

  • Tel-Aviv University, Ramat Aviv, Israel

    Dana Ron

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation