Lecture Notes in Computer Science 1444 Edited by G. Goos, J. Hartmanis and J. van Leeuwen Klaus Jansen Jos6 Rolim (Eds.) noitamixorppA smhtiroglA rof lairotanibmoC noitazimitpO International Workshop APPROX'98 Aalborg, Denmark, July 18-19, 1998 Proceedings regnirpS 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 ; Budapest ; Hong Kong ; London ; Milan ; Paris ; Singapore ; Tokyo : Springer, 1998 (Lecture notes in computer science ; Vol. 1444) ISBN 3-540-64736-8 CR Subject Classification (1991): F.2.2, G.1.2, G.1.6, G.3, 1.3.5 ISSN 0302-9743 ISBN 3-540-64736-8 Springer-Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer -Verlag. Violations are liable for prosecution under the German Copyright Law. (cid:14)9 Springer-Verlag Berlin Heidelberg 1998 Printed in Germany Typesetting: Camera-ready by author SPIN 10638075 06/3142 - 5 4 3 2 1 0 Printed on acid-free paper Preface The Workshop on Approximation Algorithms for Combinatorial Optimization smelborP APPROX'98 focuses on algorithmic and complexity aspects arising in the development of efficient approximate solutions to computationally difficult problems. It aims, in particular, at fostering cooperation among algorithmic and complexity researchers in the field. The workshop, to be held at the University of Aalborg, Denmark, on July 18 - 19, 1998, co-locates with ICALP'98. We would like to thank the organizer of ICALP'98, Kim Larsen, for this opportunity. A previous event in Europe on approximate solutions of hard combinatorial problems consisting in a school followed by a workshop was held in Udine (Italy) in 1996. Topics of interest for APPROX'98 are: design and analysis of approxima- tion algorithms, inapproximability results, on-line problems, randomization tech- niques, average-case analysis, approximation classes, scheduling problems, rout- ing and flow problems, coloring and partitioning, cuts and connectivity, packing and covering, geometric problems, network design, and various applications. The number of submitted papers to APPROX'98 was 37. Only 14 papers were se- lected. This volume contains the selected papers plus papers by invited speakers. All papers published in the workshop proceedings were selected by the program committee on the basis of referee reports. Each paper was reviewed by at least three referees who judged the papers for originality, quality, and consistency with the topics of the conference. We would like to thank all authors who responded to the call for papers and our invited speakers: Magnds M. Halld6rsson (Reykjavik), David B. Shmoys (Cornell), and Vijay V. Vazirani (Georgia Tech). Furthermore, we thank the members of the program committee: - Ed Coffman (Murray Hill), Pierluigi Crescenzi (Florence), - - Ulrich Faigle (Enschede), Michel X. Goemans (Louvain and Cambridge), - Peter Gritzmann (Mfinchen), - Magnfis M. Halld6rsson (Reykjavik), - Johan Hs (Stockholm), - Klaus Jansen (Saarbr/icken and Lugano, chair), - Claire Kenyon (Orsay), - - Andrzej Lingas (Lund), - George Lueker (Irvine), - Ernst W. Mayr (Miinchen), - Jose D.P. Rolim (Geneva, chair), Andreas Schulz (Berlin), - David B. Shmoys (Cornell), - Jan van Leeuwen (Utrecht). - IV and the reviewers Susanne Albers, Abdel-Krim Amoura, Gunnar Andersson, Christer Berg, Ioannis Caragiannis, Dietmar Cieslik, A. Clementi, Artur Czu- maj, Elias Dahlhaus, A. Del Lungo, Martin Dyer, Lars Engebretsen, Thomas Erlebach, Uriel Feige, Stefan Felsner, Rudolf Fleischer, Andras Frank, R. Grossi, Joachim Gudmundsson, Dagmar Handke, Stephan Hartmann, Dorit .S Hoch- baum, J.A. Hoogeveen, Sandra Irani, Jesper Jansson, Mark Jerrum, David John- son, Christos Kaklamanis, Hans KeUerer, Samir Khuller, Ekkehard Koehler, Ste- fano Leonardi, Joseph .S B. Mitchell, Rolf H. MShring, .S Muthu Muthukrish- nan, Petra Mutzel, Giuseppe Persiano, Joerg Rambau, Ramamoorthi Ravi, Ingo Schiermeyer, Martin Skutella, Roberto Solis-Oba, Frederik Stork, Ewald Speck- enmeyer, C.R. Subramanian, Luca Trevisan, Denis Trystram, John Tsitsiklis, Marc Uetz, Hans-Christoph Wirth, Gerhard Woeginger, Martin Wolff, Alexan- der Zelikovsky, and Uri Zwick. z We gratefully acknowledge sponsorship from the Max-Planck-Institute for Computer Science Saarbriicken (AG ,1 Prof. Mehlhorn), ALCOM-IT Algorithms and Complexity in Information Technology, and Siemens GmbH. We also thank Luca Gambardella, the research institute IDSIA Lugano, Alfred Hofmann, Anna Kramer, and Springer-Verlag for supporting our project. May 8991 Klaus Jansen Co e s Invited Talks Approximations of independent sets in graphs Magnds M. HalldSrsson Using linear programming in the design and analysis of 51 approximation algorithms: Two illustrative problems David B. Shmoys The steiner tree problem and its generalizations 33 Vijay .V Vazirani Contributed Talks Approximation schemes for covering and scheduling on 39 related machines Yossi Azar and Leah Epstein One for the price of two: A unified approach for 49 approximating covering problems Reuven Bar- Yehuda Approximation of geometric dispersion problems 63 Christoph Baur and Sdndor P. Fekete Approximating k-outconnected subgraph problems 77 Joseph Cheriyan, Tibor Jorddn and Zeev Nutov Lower bounds for on-line scheduling with precedence 89 constraints on identical machines Leah Epstein Instant recognition of half integrality and 2-approximations 99 Dorit S. Hochbaum The t - vertex cover problem: Extending the half integrality 111 framework with budget constraints Dorit .S muabhcoH vllf A new fully polynomial approximation scheme for the 321 knapsack problem Hans Kellerer and Ulrich Pferschy On the hardness of approximating spanners 531 Guy Kortsarz Approximating circular arc colouring and bandwidth 741 allocation in all-opticai ring networks Vijay Kumar Approximating maximumindependentset in k-clique-free 951 graphs IngoSchiermeyer Approximating an interval scheduling problem 961 Frits C.R. Spieksma Finding dense subgraphs with semidefinite programming 181 Anand Srivastav and Katja Wolf Best possible approximation algorithm for MAX SAT 391 with cardinality constraint Maxim I. Sviridenko Author Index 201 Approximations of Independent Sets in Graphs Magnfis M. Halld6rsson 2,1 1 Science Institute, University of Iceland, Reykjavik, Iceland. ,ih@almm is 2 Department of Informatics, University of Bergen, Norway. 1 Introduction The independent set problem is that of finding a maximum size set of mutually non-adjacent vertices in a graph. The study of independent sets, and their alter egos, cliques, has had a central place in combinatorial theory. Independent sets occur whenever we seek sets of items free of pairwise con- flicts, e.g. when scheduling tasks. Aside from numerous applications (which might be more pronounced if the problems weren't so intractable), independent sets and cliques appear frequently in the theory of computing, e.g. in interactive proof systems 6 or monotone circuit complexity 2. They form the representative problems for the class of subgraph or packing problems in graphs, are essen- tial companions of graph colorings, and form the basis of clustering, whether in terms of nearness or dispersion. As late as 1990, the literature on independent set approximations was ex- tremely sparse. In the period since Johnson 13 started the study of algorithms with good performance ratios in 1974 - and in particular showed that a whole slew of independent set algorithms had only the trivial performance ratio of n on general graphs - only one paper had appeared containing positive results ,92 aside from the special case of planar graphs 34, .8 Lower bounds were effec- tively non-existent, as while it was known that the best possible performance ratio would not be some fixed constant, there might still be a polynomial-time approximation scheme lurking somewhere. Success on proving lower bounds for Independent Set has been dramatic and received worldwide attention, including the New York Times. Progress on improved approximation algorithms has been less dramatic, but a notable body of results has been developed. The purpose of this talk is to bring some of these results together, consider the lessons learned, and hypothesize about possible future developments. The current paper is not meant to be the ultimate summary of independent set approximation algorithms, but an introduction to the performance ratios known, the strategies that have been applied, and offer glimpses of some of the results that have been proven. We prefer to study a range of algorithms, rather than seek only the best possible performance guarantee. The latter is fine as far as it goes, but is not the only thing that matters; only so much information is represented by a single number. Algorithmic strategies vary in their time requirements, temporal access to data, parallelizability, simplicity and numerous other factors that are far from irrelevant. Different algorithms may also be incomparable on different classes of graphs, e.g. depending on the size of the optimal solution. Finally, the proof techniques are perhaps the most valuable product of the analysis of heuristics. We look at a slightly random selection of approximation results in the body of the paper. A complete survey is beyond the scope of this paper but is under preparation. The primary criteria for selection was simplicity, of the algorithm and the proof. We state some observations that have not formally appeared before, give some recent results, and present simpler proofs of other results. The paper is organized as follows. We define relevant problems and definitions in the following section. In the body of the paper we present a number of par- ticular results illustrating particular algorithmic strategies: subgraph removal, semi-definite programming, partitioning, greedy algorithms and local search. We give a listing of known performance results and finish with a discussion of open issues. 2 Problems and definitions TNEDNEPEDNI SET: Given a graph G = ,V( E), find a maximum cardinality set I C V such that for each u, v E I, (u, v) (cid:127) E. The independence number of G, denoted by a(G), is the size of the maximum independent set. EUQILC PARTITION: Given a graph G -- ,V( E), find a minimum cardinality set of disjoint cliques from G that contains every vertex. TES-~t PACKING: Given a collection C of sets of size at most ~ drawn from a finite set S, find a minimum cardinality collection C ~ such that each element in S is contained in some set in g .~ These problems may also be weighted, with weights on the vertices (or on the sets in SET .)GNIKCAP A set packing instance is a case of an independent set problem. Given a set system (g, S), form a graph with a vertex for each set in g and edge between two vertices if the corresponding sets intersect. Observe that if the sets in g are of size at most ,~t then the graph contains a ~ + 1-claw, which is a subgraph consisting of a center node adjacent to n + 1 mutually non-adjacent vertices. The independent set problem in n + 1-claw free graphs slightly generalizes TES-~ ,GNIKCAP which in turn slightly generalizes LANOISNEMID-;~ .GNIHCTAM The performance ratio PA of an independent set algorithm A is given by pA =- pA(n) ~- max ")G(A a,aal=,, Notation n the number of vertices d(v) the degree of vertex v m the number of edges N(v) set of neighbors of v A maximum degree N(v) non-neighbors of v average degree A(G) the size of solution found by A f( minimum degree PA performance ratio of A a independence number clique partition number maximum claw size 3 Ramsey theory and subgraph removal The first published algorithm with a non-trivial performance ratio on general graphs was introduced in 1990. In appreciation of the heritage that the late master Erd6s left us, we give here a treatment different from Boppana and Halld6rsson 12 that more closely resembles the original Ramsey theorem of Erd6s and Szekeres 17. Ramsey (G) CliqueRemoval (G) ifG = @then return (0, 0) i+- 1 choose some v E G (Ci,Ii) +- yesmaR (G) (C1,11) +- Ramsey(N(v)) whileG ~ @do (C2,I2) --+ Ramsey(N(v)) G+-G-C~ return (larger of IC( U {v}, C2), i+-i+l larger of (Ix, 21 U {v})) (C~,Ii) ~- yesmaR (g) od return ((ma,xj.= 1 Ij), {Cz, C2, ..., Ci}) Fig. 1. Independent set algorithm based on Ramsey theory Theorem 1. Ramsey finds an independent set I and a clique C such that 11+11/I( cl) - 1 > n. In particular, I/1" ICI _> 1 log2 n. Proof. The proof is by induction on both II I and ICI. It is easy to verify the claim when either III or ICI are at most 1. By the induction hypothesis, n= N(v)l + lN(v), + X _< ((111'1Cl11Cl1)-1)+ ((1121+1C21-1)-1)+1.16,21 Recall that ICl = max(lOll + 1, IC21) and I/I = max(lI11, 12/1 + 1). Thus, n_ -1) + (III+ICI- 1) - < C'I IcIICI 1 ICI 1. The claim now follows from the equality (8+t) = (8+t-l~ + ( s-t-t--1 t ) xs~ kt--l!