Research Catalog

Title

Approximation algorithms for combinatorial optimization : international ICALP '98 workshop, APPROX '98, Aalborg, Denmark, July 18-19, 1998 : proceedings / Klaus Jansen, José Rolim, eds.

Publication

New York : Springer, 1998.

Items in the Library & Off-site

Holdings

Details

Additional Authors

• Jansen, Klaus.
• Rolim, José D. P.
• International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (1998 : Ålborg, Denmark)

Description

viii, 199 pages : illustrations; 24 cm.

Series Statement

Lecture notes in computer science ; 1444

Uniform Title

Lecture notes in computer science ; 1444.

Subject

• Computer algorithms > Congresses
• Approximation theory > Data processing > Congresses
• Combinatorial optimization > Data processing > Congresses

Note

• Selected papers from APPROX '98, held July 18-19, 1998, University of Aalborg, Denmark, in conjunction with ICALP '98.

Bibliography (note)

• Includes bibliographical references and index.

Contents

• Approximations of independent sets in graphs / Magnus M. Halldorsson -- Using linear programming in the design and analysis of approximation algorithms: Two illustrative problems / David B. Shmoys -- The steiner tree problem and its generalizations / Vijay V. Vazirani -- Approximation schemes for covering and scheduling on related machines / Yossi Azar and Leah Epstein -- One for the price of two: A unified approach for approximating covering problems / Reuven Bar-Yehuda -- Approximation of geometric dispersion problems / Christoph Baur and Sandor P. Fekete -- Approximating k-outconnected subgraph problems / Joseph Cheriyan, Tibor Jordan and Zeev Nutov -- Lower bounds for on-line scheduling with precedence constraints on identical machines / Leah Epstein -- Instant recognition of half integrality and 2-approximations / Dorit S. Hochbaum -- The t-vertex cover problem: Extending the half integrality framework with budget constraints / Dorit S. Hochbaum --
• A new fully polynomial approximation scheme for the knapsack problem / Hans Kellerer and Ulrich Pferschy -- On the hardness of approximating spanners / Guy Kortsarz -- Approximating circular arc colouring and bandwidth allocation in all-optical ring networks / Vijay Kumar -- Approximating maximum independent set in k-clique-free graphs / Ingo Schiermeyer -- Approximating an interval scheduling problem / Frits C. R. Spieksma -- Finding dense subgraphs with semidefinite programming / Anand Srivastav and Katja Wolf -- Best possible approximation algorithm for MAX SAT with cardinality constraint / Maxim I. Sviridenko.

ISBN

3540647368 (softcover :alk. paper)

LCCN

98034217

OCLC

• 474797524
• ocn474797524

Owning Institutions

Columbia University Libraries