1 option
Approximation Algorithms for Combinatorial Optimization : International Workshop APPROX'98, Aalborg, Denmark, July 18-19, 1998, Proceedings / edited by Klaus Jansen, Jose Rolim.
LIBRA Q341 .P7 2004
Available from offsite location
- Format:
- Book
- Series:
- Computer Science (Springer-11645)
- Lecture notes in computer science 0302-9743 ; 1444.
- Lecture Notes in Computer Science, 0302-9743 ; 1444
- Language:
- English
- Subjects (All):
- Computers.
- Algorithms.
- Computer science--Mathematics.
- Computer science.
- Calculus of variations.
- Computer graphics.
- Theory of Computation.
- Algorithm Analysis and Problem Complexity.
- Discrete Mathematics in Computer Science.
- Calculus of Variations and Optimal Control; Optimization.
- Computer Graphics.
- Local Subjects:
- Theory of Computation.
- Algorithm Analysis and Problem Complexity.
- Discrete Mathematics in Computer Science.
- Calculus of Variations and Optimal Control; Optimization.
- Computer Graphics.
- Physical Description:
- 1 online resource (IX, 207 pages).
- Edition:
- First edition 1998.
- Contained In:
- Springer eBooks
- Place of Publication:
- Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 1998.
- System Details:
- text file PDF
- Summary:
- 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.
- Contents:
- 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.
- Other Format:
- Printed edition:
- ISBN:
- 978-3-540-69067-2
- 9783540690672
- Access Restriction:
- Restricted for use by site license.
The Penn Libraries is committed to describing library materials using current, accurate, and responsible language. If you discover outdated or inaccurate language, please fill out this feedback form to report it and suggest alternative language.