Skip to main content
SpringerLink
Log in
Book cover

Approximation Algorithms for Combinatorial Optimization

5th International Workshop, APPROX 2002, Rome, Italy, September 17-21, 2002. Proceedings

  • Conference proceedings
  • © 2002

Overview

Editors:
  1. Klaus Jansen

    1. Institut für Informatik und praktische Mathematik, Universität Kiel, Kiel, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Stefano Leonardi

    1. Dipartimento di Informatika e Sistemistica, Universita di Roma La Sapienza, Roma, Italy

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Vijay Vazirani

    1. College of Computing, Georgia Institute of Technology, Georgia, USA

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

Included in the following conference series:

Conference proceedings info: APPROX 2002.

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

  1. Front Matter

    Pages I-VIII
    Download chapter PDF

  2. Search and Classification of High Dimensional Data

    • Yuval Rabani
    Pages 1-2

  3. Bicriteria Spanning Tree Problems

    • R. Ravi
    Pages 3-4

  4. Improved Approximation Algorithms for Multilevel Facility Location Problems

    • Alexander Ageev
    Pages 5-13

  5. On Constrained Hypergraph Coloring and Scheduling

    • Nitin Ahuja, Anand Srivastav
    Pages 14-25

  6. On the Power of Priority Algorithms for Facility Location and Set Cover

    • Spyros Angelopoulos, Allan Borodin
    Pages 26-39

  7. Two Approximation Algorithms for 3-Cycle Covers

    • Markus Bläser, Bodo Manthey
    Pages 40-50

  8. Approximation Algorithms for the Unsplittable Flow Problem

    • Amit Chakrabarti, Chandra Chekuri, Anuptam Gupta, Amit Kumar
    Pages 51-66

  9. 1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor

    • Erik D. Demaine, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos
    Pages 67-80

  10. Typical Rounding Problems

    • Benjamin Doerr
    Pages 81-93

  11. Approximating Min-sum Set Cover

    • Uriel Feige, László Lovász, Prasad Tetali
    Pages 94-107

  12. Approximating Maximum Edge Coloring in Multigraphs

    • Uriel Feige, Eran Ofek, Udi Wieder
    Pages 108-121

  13. Approximating the Complement of the Maximum Compatible Subset of Leaves of k Trees

    • Ganeshkumar Ganapathy, Tandy Warnow
    Pages 122-134

  14. A 27/26-Approximation Algorithm for the Chromatic Sum Coloring of Bipartite Graphs

    • Krzysztof Giaro, Robert Janczewski, Marek Kubale, Michał Małafiejski
    Pages 135-145

  15. Facility Location and the Geometric Minimum-Diameter Spanning Tree

    • Joachim Gudmundsson, Herman Haverkort, Sang-Min Park, Chan-Su Shin, Alexander Wolff
    Pages 146-160

  16. Improved Approximation Algorithms for the Partial Vertex Cover Problem

    • Eran Halperin, Aravind Srinivasan
    Pages 161-174

  17. Minimum Restricted Diameter Spanning Trees

    • Refael Hassin, Asaf Levin
    Pages 175-184

  18. Hardness of Approximation for Vertex-Connectivity Network-Design Problems

    • Guy Kortsarz, Robert Krauthgamer, James R. Lee
    Pages 185-199

  19. Non-abusiveness Helps: An % MathType!MTEF!2!1!+- % feaafiart1ev1aaatCvAUfKttLearuqr1ngBPrgarmWu51MyVXgatC % vAUfeBSjuyZL2yd9gzLbvyNv2CaeHbuLwBLnhiov2DGi1BTfMBaeHb % d9wDYLwzYbItLDharqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbb % L8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs0-yqaqpe % pae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaaiaadeWaaq % aadaqbaaGcbaGaaGOmamaaCaaaleqabaGagiiBaWMaei4Ba8Maei4z % aCgaaOWaaWbaaSqabeaadaahaaadbeqaamaaBaaabaWaaWbaaeqaba % GaaGymaiabgkHiTiabgIGiodaaaeqaaaaaaaGcdaahaaWcbeqaaiab % d6gaUbaaaaa!4546! \[ 2^{\log } ^{^{_{^{1 - \in } } } } ^n \] (1)-Competitive Algorithm for Minimizing the Maximum Flow Time in the Online Traveling Salesman Problem

    • Sven O. Krumke, Luigi Laura, Maarten Lipmann, Alberto Marchetti-Spaccamela, Willem E. de Paepe, Diana Poensgen et al.
    Pages 200-214

  20. Routing and Admission Control in Networks with Advance Reservations

    • Liane Lewin-Eytan, Joseph Seffi Naor, Ariel Orda
    Pages 215-228
Back to top

Other volumes

  1. Approximation Algorithms for Combinatorial Optimization

Keywords

Editors and Affiliations

  • Institut für Informatik und praktische Mathematik, Universität Kiel, Kiel, Germany

    Klaus Jansen

  • Dipartimento di Informatika e Sistemistica, Universita di Roma La Sapienza, Roma, Italy

    Stefano Leonardi

  • College of Computing, Georgia Institute of Technology, Georgia, USA

    Vijay Vazirani

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation