Approximation Algorithms for Combinatiorial Optimization: International Workshop APPROX'98 Aalborg, Denmark, July 18–19, 1998 Proceedings

✍ Scribed by MagnÚs M. Halldórsson (auth.), Klaus Jansen, José Rolim (eds.)

Publisher: Springer-Verlag Berlin Heidelberg
Year: 1998
Tongue: English
Leaves: 202
Series: Lecture Notes in Computer Science 1444
Edition: 1
Category: Library

No coin nor oath required. For personal study only.

✦ Synopsis

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.

✦ Table of Contents

Approximations of independent sets in graphs....Pages 1-13
Using linear programming in the design and analysis of approximation algorithms: Two illustrative problems....Pages 15-32
The Steiner tree problem and its generalizations....Pages 33-38
Approximation schemes for covering and scheduling in related machines....Pages 39-47
One for the price of two: A unified approach for approximating covering problems....Pages 49-62
Approximation of geometric dispersion problems....Pages 63-75
Approximating k -outconnected subgraph problems....Pages 77-88
Lower bounds for on-line scheduling with precedence constraints on identical machines....Pages 89-98
Instant recognition of half integrality and 2-approximations....Pages 99-110
The t -vertex cover problem: Extending the half integrality framework with budget constraints....Pages 111-122
A new fully polynomial approximation scheme for the knapsack problem....Pages 123-134
On the hardness of approximating spanners....Pages 135-146
Approximating circular arc colouring and bandwidth allocation in all-optical ring networks....Pages 147-158
Approximating maximum independent set in k-clique-free graphs....Pages 159-168
Approximating an interval scheduling problem....Pages 169-180
Finding dense subgraphs with semidefinite programming....Pages 181-191
Best possible approximation algorithm for MAX SAT with cardinality constraint....Pages 193-199

✦ Subjects

Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Calculus of Variations and Optimal Control; Optimization; Computer Graphics

📜 SIMILAR VOLUMES

Approximation Algorithms for Combinatior

📁 Approximation Algorithms for Combinatiorial Optimization: International Workshop APPROX'98 Aalborg, Denmark, July 18–19, 1998 Proceedings

✍ MagnÚs M. Halldórsson (auth.), Klaus Jansen, José Rolim (eds.) 📂 Library 📅 1998 🏛 Springer-Verlag Berlin Heidelberg 🌐 English

<p>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.<BR>The volume presents 14 revised full papers together with three invited paper

Approximation Algorithms for Combinatori

📁 Approximation Algorithms for Combinatorial Optimization: 5th International Workshop, APPROX 2002 Rome, Italy, September 17–21, 2002 Proceedings

✍ Yuval Rabani (auth.), Klaus Jansen, Stefano Leonardi, Vijay Vazirani (eds.) 📂 Library 📅 2002 🏛 Springer-Verlag Berlin Heidelberg 🌐 English

This book constitutes the refereed proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002, held in Rome, Italy in September 2002.<BR>The 20 revised full papers presented were carefully reviewed and selected from 54 submissions.

Approximation Algorithms for Combinatori

📁 Approximation Algorithms for Combinatorial Optimization: 5th International Workshop, APPROX 2002 Rome, Italy, September 17–21, 2002 Proceedings

✍ Yuval Rabani (auth.), Klaus Jansen, Stefano Leonardi, Vijay Vazirani (eds.) 📂 Library 📅 2002 🏛 Springer-Verlag Berlin Heidelberg 🌐 English

Approximation Algorithms for Combinatori

📁 Approximation Algorithms for Combinatorial Optimization: Third International Workshop, APPROX 2000 Saarbrücken, Germany, September 5–8, 2000 Proceedings

✍ Sanjeev Arora (auth.), Klaus Jansen, Samir Khuller (eds.) 📂 Library 📅 2000 🏛 Springer-Verlag Berlin Heidelberg 🌐 English

This book constitutes the refereed proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2000, held in Saarbr?cken, Germany in September 2000. The 22 revised full papers presented together with four invited contributions were care

Approximation Algorithms for Combinatori

📁 Approximation Algorithms for Combinatorial Optimization: Third International Workshop, APPROX 2000 Saarbrücken, Germany, September 5–8, 2000 Proceedings

✍ Sanjeev Arora (auth.), Klaus Jansen, Samir Khuller (eds.) 📂 Library 📅 2000 🏛 Springer-Verlag Berlin Heidelberg 🌐 English

Approximation, Randomization, and Combin

📁 Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques: 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 Berkeley, CA, USA, August 18–20, 2001 Proceedings

✍ Michel X. Goemans (auth.), Michel Goemans, Klaus Jansen, José D. P. Rolim, Luca 📂 Library 📅 2001 🏛 Springer-Verlag Berlin Heidelberg 🌐 English

<p>This book constitutes the joint refereed proceedings of the 4th International Workshop on Approximation Algorithms for Optimization Problems, APPROX 2001 and of the 5th International Workshop on Ranomization and Approximation Techniques in Computer Science, RANDOM 2001, held in Berkeley, Californ