Skip to main content
SpringerLink
Log in

Approximation Algorithms for Combinatorial Optimization

International Workshop APPROX'98, Aalborg, Denmark, July 18-19, 1998, Proceedings

  • Conference proceedings
  • © 1998

Overview

Editors:
  1. Klaus Jansen
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. José Rolim
    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 1444)

Included in the following conference series:

Conference proceedings info: APPROX 1998.

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

Access this book

Log in via an institution
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 (17 papers)

  1. Front Matter

    Download chapter PDF

  2. Approximations of independent sets in graphs

    • MagnÚs M. Halldórsson
    Pages 1-13

  3. Using linear programming in the design and analysis of approximation algorithms: Two illustrative problems

    • David B. Shmoys
    Pages 15-32

  4. The Steiner tree problem and its generalizations

    • Vijay V. Vazirani
    Pages 33-38

  5. Approximation schemes for covering and scheduling in related machines

    • Yossi Azar, Leah Epstein
    Pages 39-47

  6. One for the price of two: A unified approach for approximating covering problems

    • Reuven Bar-Yehuda
    Pages 49-62

  7. Approximation of geometric dispersion problems

    • Christoph Baur, Sándor P. Fekete
    Pages 63-75

  8. Approximating k-outconnected subgraph problems

    • Joseph Cheriyan, Tibor Jordán, Zeev Nutov
    Pages 77-88

  9. Lower bounds for on-line scheduling with precedence constraints on identical machines

    • Leah Epstein
    Pages 89-98

  10. Instant recognition of half integrality and 2-approximations

    • Dorit S. Hochbaum
    Pages 99-110

  11. The t-vertex cover problem: Extending the half integrality framework with budget constraints

    • Dorit S. Hochbaum
    Pages 111-122

  12. A new fully polynomial approximation scheme for the knapsack problem

    • Hans Kellerer, Ulrich Pferschy
    Pages 123-134

  13. On the hardness of approximating spanners

    • Guy Kortsarz
    Pages 135-146

  14. Approximating circular arc colouring and bandwidth allocation in all-optical ring networks

    • Vijay Kumar
    Pages 147-158

  15. Approximating maximum independent set in k-clique-free graphs

    • Ingo Schiermeyer
    Pages 159-168

  16. Approximating an interval scheduling problem

    • Frits C. R. Spieksma
    Pages 169-180

  17. Finding dense subgraphs with semidefinite programming

    • Anand Srivastav, Katja Wolf
    Pages 181-191

  18. Best possible approximation algorithm for MAX SAT with cardinality constraint

    • Maxim I. Sviridenko
    Pages 193-199
Back to top

Other volumes

  1. Approximation Algorithms for Combinatiorial Optimization

Keywords

About this book

This book constitutes the refereed proceedings of the International Workshop on Approximation Algorithms for Combinatorical Optimization, APPROX'98, held in conjunction with ICALP'98 in Aalborg, Denmark, in July 1998.
The volume presents 14 revised full papers together with three invited papers selected from 37 submissions. The papers address the design and analysis of approximation algorithms, inapproximability results, on-line problems, randomization techniques, average-case analysis, approximation classes, scheduling problems, routing and flow problems, coloring and partitioning, cuts and connectivity, packing and covering, geometric problems, network design, and various applications.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation