Skip to main content
SpringerLink
Log in
Book cover

Approximation Algorithms for Combinatorial Optimization

Third International Workshop, APPROX 2000 Saarbrücken, Germany, September 5-8, 2000 Proceedings

  • Conference proceedings
  • © 2000

Overview

Editors:
  1. Klaus Jansen

    1. Christian-Albrechts-Universität zu Kiel Institut für Informatik und praktische Mathematik Olshausenstr, Kiel, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Samir Khuller

    1. Computer Science Department, University of Maryland, 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 1913)

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

  1. Front Matter

    Pages I-IX
    Download chapter PDF

  3. Contributed Talks

    1. An Approximation Algorithm for MAX DICUT with Given Sizes of Parts

      • Alexander Ageev, Refael Hassin, Maxim Sviridenko
      Pages 34-41

    2. Maximizing Job Benefits On-Line

      • Baruch Awerbuch, Yossi Azar, Oded Regev
      Pages 42-50

    3. Variable Length Sequencing with Two Lengths

      • Piotr Berman, Junichiro Fukuyama
      Pages 51-59

    4. Randomized Path Coloring on Binary Trees

      • Vincenzo Auletta, Ioannis Caragiannis, Christos Kaklamanis, Pino Persiano
      Pages 60-71

    5. Wavelength Rerouting in Optical Networks, or the Venetian Routing Problem

      • Alberto Caprara, Giuseppe F. Italiano, G. Mohan, Alessandro Panconesi, Aravind Srinivasan
      Pages 72-83

    6. Greedy Approximation Algorithms for Finding Dense Components in a Graph

      • Moses Charikar
      Pages 84-95

    7. Online Real-Time Preemptive Scheduling of Jobs with Deadlines

      • Bhaskar DasGupta, Michael A. Palis
      Pages 96-107

    8. On the Relative Complexity of Approximate Counting Problems

      • Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, Mark Jerrum
      Pages 108-119

    9. On the Hardness of Approximating NP Witnesses

      • Uriel Feige, Michael Langberg, Kobbi Nissim
      Pages 120-131

    10. Maximum Dispersion and Geometric Maximum Weight Cliques

      • Sándor P. Fekete, Henk Meijer
      Pages 132-141

    11. New Results for Online Page Replication

      • Rudolf Fleischer, Steve Seiden
      Pages 144-154

    12. Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses

      • Venkatesan Guruswami
      Pages 155-166

    13. Approximation Algorithms for a Capacitated Network Design Problem

      • R. Hassin, R. Ravi, F. S. Salman
      Pages 167-176

    14. An Approximation Algorithm for the Fault Tolerant Metric Facility Location Problem

      • Kamal Jain, Vijay V. Vazirani
      Pages 177-182

    15. Improved Approximations for Tour and Tree Covers

      • Jochen Könemann, Goran Konjevod, Ojas Parekh, Amitabh Sinha
      Pages 184-193
Back to top

Keywords

Editors and Affiliations

  • Christian-Albrechts-Universität zu Kiel Institut für Informatik und praktische Mathematik Olshausenstr, Kiel, Germany

    Klaus Jansen

  • Computer Science Department, University of Maryland, USA

    Samir Khuller

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation