Skip to main content
SpringerLink
Log in
Book cover
  • Conference proceedings
  • © 2003

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

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)

Conference series link(s): APPROX: International Workshop on Approximation Algorithms for Combinatorial Optimization, RANDOM: International Workshop on Randomization and Approximation Techniques in Computer Science

Conference proceedings info: APPROX 2003, RANDOM 2003.

Sections

Buy it now

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

This is a preview of subscription content, log in via an institution to check for access.

Table of contents (33 papers)

  1. Front Matter

    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

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

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

    14. Effective Routing and Scheduling in Adversarial Queueing Networks

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

  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

Back to top

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.

Back to top

Keywords

Back to top

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

Back to top

Bibliographic Information

Back to top

Publish with us

Policies and ethics

Back to top
Access via your institution

Buy it now

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

Search

Navigation