Skip to main content
SpringerLink
Log in
Book cover

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, Princeto, NY, USA, August 24-26,2003

  • Conference proceedings
  • © 2003

Overview

Editors:
  1. Sanjeev Arora

    1. Computer Science Department, Princeton University, Princeton

    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. Amit Sahai

    1. University of California, Los Angeles

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

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

  1. Front Matter

    Download chapter PDF

  2. Contributed Talks of APPROX

    1. Correlation Clustering with Partial Information

      • Erik D. Demaine, Nicole Immorlica
      Pages 1-13

    2. Improved Linear Time Approximation Algorithms for Weighted Matchings

      • Doratha E. Drake, Stefan Hougardy
      Pages 14-23

    3. Covering Graphs Using Trees and Stars

      • G. Even, N. Garg, J. Könemann, R. Ravi, A. Sinha
      Pages 24-35

    4. An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor

      • Jittat Fakcharoenphol, Kunal Talwar
      Pages 36-46

    5. Approximation Algorithms for Channel Allocation Problems in Broadcast Networks

      • Rajiv Gandhi, Samir Khuller, Aravind Srinivasan, Nan Wang
      Pages 47-58

    6. Asymmetry in k-Center Variants

      • Inge Li Gørtz, Anthony Wirth
      Pages 59-70

    7. An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times

      • Alex Hall, Katharina Langkau, Martin Skutella
      Pages 71-82

    8. On the Complexity of Approximating k-Dimensional Matching

      • Elad Hazan, Shmuel Safra, Oded Schwartz
      Pages 83-97

    9. Approximating Market Equilibria

      • Kamal Jain, Mohammad Mahdian, Amin Saberi
      Pages 98-108

    10. Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem

      • Jochen Könemann, Asaf Levin, Amitabh Sinha
      Pages 109-121

    11. On the Hardness of Approximate Multivariate Integration

      • Ioannis Koutis
      Pages 122-128

    12. A 2-Approximation Algorithm for the Soft-Capacitated Facility Location Problem

      • Mohammad Mahdian, Yinyu Ye, Jiawei Zhang
      Pages 129-140

    13. Approximating Rooted Connectivity Augmentation Problems

      • Zeev Nutov
      Pages 141-152

    14. Effective Routing and Scheduling in Adversarial Queueing Networks

      • Jay Sethuraman, Chung-Piaw Teo
      Pages 153-164

    15. Approximation Schemes for Generalized 2-Dimensional Vector Packing with Application to Data Placement

      • Hadas Shachnai, Tami Tamir
      Pages 165-177

    16. An Improved Algorithm for Approximating the Radii of Point Sets

      • Yinyu Ye, Jiawei Zhang
      Pages 178-187

  3. Contributed Talks of RANDOM

    1. Testing Low-Degree Polynomials over GF(2)

      • Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
      Pages 188-199

    2. Computational Analogues of Entropy

      • Boaz Barak, Ronen Shaltiel, Avi Wigderson
      Pages 200-215

    3. Bounds on 2-Query Codeword Testing

      • Eli Ben-Sasson, Oded Goldreich, Madhu Sudan
      Pages 216-227
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 6th International Workshop on Approximation Algorithms for Optimization Problems, APPROX 2003 and of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, held in Princeton, NY, USA in August 2003.

The 33 revised full papers presented were carefully reviewed and selected from 74 submissions. Among the issues addressed are design and analysis of randomized and approximation algorithms, online algorithms, complexity theory, combinatorial structures, error-correcting codes, pseudorandomness, derandomization, network algorithms, random walks, Markov chains, probabilistic proof systems, computational learning, randomness in cryptography, and various applications.

Editors and Affiliations

  • Computer Science Department, Princeton University, Princeton

    Sanjeev Arora

  • 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

  • University of California, Los Angeles

    Amit Sahai

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation