Approximation Algorithms for Combinatorial Optimization: International Workshop APPROX'98, Aalborg, Denmark, July 18-19, 1998, Proceedings - Softcover

Softcover

ISBN 10: 3662191989 ISBN 13: 9783662191989

Publisher: Springer, 2014

Synopsis

Approximations of independent sets in graphs.- Using linear programming in the design and analysis of approximation algorithms: Two illustrative problems.- The Steiner tree problem and its generalizations.- Approximation schemes for covering and scheduling in related machines.- One for the price of two: A unified approach for approximating covering problems.- Approximation of geometric dispersion problems.- Approximating k-outconnected subgraph problems.- Lower bounds for on-line scheduling with precedence constraints on identical machines.- Instant recognition of half integrality and 2-approximations.- The t-vertex cover problem: Extending the half integrality framework with budget constraints.- A new fully polynomial approximation scheme for the knapsack problem.- On the hardness of approximating spanners.- Approximating circular arc colouring and bandwidth allocation in all-optical ring networks.- Approximating maximum independent set in k-clique-free graphs.- Approximating an interval scheduling problem.- Finding dense subgraphs with semidefinite programming.- Best possible approximation algorithm for MAX SAT with cardinality constraint.

Edition details

• Publisher: Springer
• Publication date: 2014
• ISBN 10: 3662191989
• ISBN 13: 9783662191989
• Binding: Paperback
• Language: English
• Number of pages: 216
• Editor: Jansen Klaus, Rolim Jose