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.
Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis and J. van Leeuwen
1444
Klaus Jansen Jos6 Rolim (Eds.)
Approximation Algorithms for Combinatorial Optimization International Workshop APPROX'98 Aalborg, Denmark, July 18-19, 1998 Proceedings
Springer
Series Editors Gerhard Goos, Karlsruhe University, Germany Juris Hartmanis, Cornell University, NY, USA Jan van Leeuwen, Utrecht University, The Netherlands Volume Editors Klaus Jansen IDSIA Lugano Corso Elvezia 36, CH-6900 Lugano, Switzerland E-mail:
[email protected] Jos6 Rolim University of Geneva, Computer Science Center 23, Rue Gtntral Dufour, CH-1211 Geneva 4, Switzerland E-mail: jose.rolim @cui.unige.ch Cataloging-in-Publication data applied for
Die Deutsche Bibliothek - CIP-Einheitsaufuahme
Approximation algorithms for combinatorial optimization : proceedings / International ICALP '98 Workshop, APPROX '98, Aalborg, Denmark, July 18 - 19, 1998. Klaus Jansen ; Jos~ Rolim (ed.). - Berlin ; Heidelberg ; New York ; Barcelona ; B