Lecture Notes in Computer Science 3879 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen UniversityofDortmund,Germany MadhuSudan MassachusettsInstituteofTechnology,MA,USA DemetriTerzopoulos NewYorkUniversity,NY,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA MosheY.Vardi RiceUniversity,Houston,TX,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany Thomas Erlebach Giuseppe Persiano (Eds.) Approximation and Online Algorithms Third International Workshop, WAOA 2005 Palma de Mallorca, Spain, October 6-7, 2005 Revised Papers 1 3 VolumeEditors ThomasErlebach UniversityofLeicester DepartmentofComputerScience UniversityRoad,Leicester,LE17RH,UK E-mail:[email protected] GiuseppePersiano UniversitàdegliStudidiSalerno DipartimentodiInformaticaedApplicazioni ViaS.Allende2,84081Baronissi(SA),Italy E-mail:[email protected] LibraryofCongressControlNumber:200692553 CRSubjectClassification(1998):F.2.2,G.2.1-2,G.1.2,G.1.6,I.3.5,E.1 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ISSN 0302-9743 ISBN-10 3-540-32207-8SpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-32207-8SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. SpringerisapartofSpringerScience+BusinessMedia springer.com ©Springer-VerlagBerlinHeidelberg2006 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SPIN:11671411 06/3142 543210 Preface The third Workshop on Approximation and Online Algorithms (WAOA 2005) focused on the design and analysis of algorithms for online and computationally hardproblems.Bothkindsofproblemshavealargenumberofapplicationsfrom a variety of fields. WAOA 2005 took place in Palma de Mallorca, Spain, on 6–7 October2005.TheworkshopwaspartoftheALGO2005eventthatalsohosted ESA, WABI, and ATMOS. The two previous WAOA workshops were held in Budapest (2003) and Rome (2004). Topics of interest for WAOA 2005 were: algorithmic game theory, approxi- mation classes, coloring and partitioning, competitive analysis, computational finance, cuts and connectivity, geometric problems, inapproximability results, mechanism design, network design, packing and covering, paradigms, random- izationtechniques,real-worldapplications,andschedulingproblems.Inresponse tothecallforpaperswereceived68submissions.Eachsubmissionwasreviewed by at least three referees, and the vast majority by at least four referees. The submissions were mainly judged on originality, technical quality, and relevance to the topics of the conference. Based on the reviews, the Program Committee selected 26 papers. We are grateful to Andrei Voronkov for providing the EasyChair conference system,whichwasusedtomanagetheelectronicsubmissions,thereviewprocess, and the electronic PC meeting. It made our task much easier. We would also like to thank all the authors who submitted papers to WAOA 2005 as well as the local organizers of ALGO 2005. November 2005 T. Erlebach G. Persiano Organization Program Co-chairs Thomas Erlebach University of Leicester Giuseppe Persiano Universita` di Salerno Program Committee Evripidis Bampis University of Evry Markus Bla¨ser ETH Zu¨rich Thomas Erlebach University of Leicester Klaus Jansen Universita¨t Kiel Christos Kaklamanis University of Patras Marc van Kreveld Utrecht University Pino Persiano Universita` di Salerno Guido Proietti Universita` di L’Aquila Kirk Pruhs University of Pittsburgh Yuval Rabani Technion, Haifa Adi Ros´en Technion, Haifa Martin Skutella Universita¨t Dortmund Roberto Solis-Oba University of Western Ontario Frits Spieksma Katholieke Universiteit Leuven Berthold V¨ocking RWTH Aachen Referees Helmut Alt Joan Boyar Jurriaan Hage Ernst Althaus Ioannis Caragiannis Han Hoogeveen Pasquale Ambrosio Reuven Cohen Sandy Irani Eric Angel Jos´e Correa Panagiotis Kanellopoulos Claudio Arbib Yves Crama Lasse Kliemann Estie Arkin Roberto De Prisco Christian Knauer Takao Asano Florian Diedrich Reinhard Koch Vincenzo Auletta Benjamin Doerr Ronald Koch Yossi Azar Leah Epstein Ekkehard Ko¨hler Fabien Baille Aleksei Fishkin Jochen Ko¨nemann Reuven Bar-Yehuda Luca Forlizzi Alexander Kononov Nadine Baumann Stefan Funke Elias Koutsoupias Davide Bilo` Olga Gerber Annamaria Kovacs Vittorio Bilo` Laurent Gourv`es Sofia Kovaleva Hans Bodlaender Luciano Guala` Darek Kowalski VIII Organization Christian Laforest Evi Papaioannou Csaba To´th Van Bang Le Paolo Penna Marc Uetz Stefano Leonardi L. Shankar Ram Carmine Ventre Gitta Marchand Fabrizio Rossi Tjark Vredeveld Maren Martens Guido Scha¨fer Egon Wanke Giovanna Melideo Stefano Smriglio Gerhard Woeginger Joe Mitchell Rob van Stee Guochuan Zhang Luca Moscardelli Gerard Tel Michele Zito Alfredo Navarra Nicolas Thibault Ren´e van Oostrum Ralf Tho¨le Table of Contents “Almost Stable” Matchings in the Roommates Problem David J. Abraham, P´eter Biro´, David F. Manlove................. 1 On the Minimum Load Coloring Problem Nitin Ahuja, Andreas Baltz, Benjamin Doerr, Aleˇs Pˇr´ıvˇetiv´y, Anand Srivastav .............................................. 15 Improved Approximation Algorithms for MAX NAE-SAT and MAX SAT Adi Avidor, Ido Berkovitch, Uri Zwick........................... 27 The Hardness of Network Design for Unsplittable Flow with Selfish Users Yossi Azar, Amir Epstein ...................................... 41 Improved Approximation Algorithm for Convex Recoloring of Trees Reuven Bar-Yehuda, Ido Feldman, Dror Rawitz................... 55 Exploiting Locality: Approximating Sorting Buffers Reuven Bar-Yehuda, Jonathan Laserson ......................... 69 Approximate Fair Cost Allocation in Metric Traveling Salesman Games M. Bla¨ser, L. Shankar Ram .................................... 82 Rounding of Sequences and Matrices, with Applications Benjamin Doerr, Tobias Friedrich, Christian Klein, Ralf Osbild..... 96 A Note on Semi-online Machine Covering Toma´ˇs Ebenlendr, John Noga, Jiˇr´ı Sgall, Gerhard Woeginger ....... 110 SONET ADMs Minimization with Divisible Paths Leah Epstein, Asaf Levin ...................................... 119 The Conference Call Search Problem in Wireless Networks Leah Epstein, Asaf Levin ...................................... 133 Improvements for Truthful Mechanisms with Verifiable One-Parameter Selfish Agents A. Ferrante, G. Parlato, F. Sorrentino, C. Ventre................. 147 Symmetry in Network Congestion Games: Pure Equilibria and Anarchy Cost Dimitris Fotakis, Spyros Kontogiannis, Paul Spirakis .............. 161 X Table of Contents A Better-Than-Greedy Algorithm for k-Set Multicover Toshihiro Fujito, Hidekazu Kurahashi ........................... 176 Deterministic Online Optical Call Admission Revisited Elisabeth Gassner, Sven O. Krumke ............................. 190 Scheduling Parallel Jobs with Linear Speedup Alexander Grigoriev, Marc Uetz ................................ 203 Online Removable Square Packing Xin Han, Kazuo Iwama, Guochuan Zhang ....................... 216 The Online Target Date Assignment Problem S. Heinz, S.O. Krumke, N. Megow, J. Rambau, A. Tuchscherer, T. Vredeveld ................................................. 230 Approximation and Complexity of k–Splittable Flows Ronald Koch, Martin Skutella, Ines Spenke....................... 244 On Minimizing the Maximum Flow Time in the Online Dial-a-Ride Problem Sven O. Krumke, Willem E. de Paepe, Diana Poensgen, Maarten Lipmann, Alberto Marchetti-Spaccamela, Leen Stougie ..... 258 Tighter Approximations for Maximum Induced Matchings in Regular Graphs Zvi Gotthilf, Moshe Lewenstein ................................. 270 On Approximating Restricted Cycle Covers Bodo Manthey ................................................ 282 A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs Tim Nieberg, Johann Hurink ................................... 296 Speed Scaling of Tasks with Precedence Constraints Kirk Pruhs, Rob van Stee, Patchrawat Uthaisombut ............... 307 Partial Multicuts in Trees Asaf Levin, Danny Segev ...................................... 320 Approximation Schemes for Packing with Item Fragmentation Hadas Shachnai, Tami Tamir, Omer Yehezkely ................... 334 Author Index.................................................. 349 “Almost Stable” Matchings in the Roommates Problem David J. Abraham1,(cid:1), P´eter Biro´2,(cid:1)(cid:1), and David F. Manlove3,(cid:1)(cid:1)(cid:1) 1Computer ScienceDepartment, Carnegie-Mellon University,USA [email protected] 2Department of Algebra, and Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Hungary [email protected] 3Department of Computing Science, University of Glasgow, UK [email protected] Abstract. AninstanceoftheclassicalStableRoommatesproblem(sr) neednotadmitastablematching.Thismotivatestheproblemoffinding amatchingthatis“asstableaspossible”,i.e.admitsthefewestnumber ofblockingpairs.Inthispaperweprovethat,givenansrinstancewithn agents, inwhich allpreferencelists arecomplete, theproblem offinding amatchingwiththefewestnumberofblockingpairsisNP-hardandnot approximablewithinn12−ε,foranyε>0,unlessP=NP.Ifthepreference lists contain ties, we improve this result to n1−ε. Also, we show that, given anintegerK andan sr instanceI in which allpreferencelists are complete, the problem of deciding whether I admits a matching with exactly K blocking pairs is NP-complete. By contrast, if K is constant, wegiveapolynomial-timealgorithmthatfindsamatchingwithatmost (or exactly) K blocking pairs, or reports that no such matching exists. Finally, we give upper and lower bounds for the minimum number of blockingpairsoverallmatchingsin termsofsomeproperties ofastable partition, given an sr instance I. 1 Introduction The Stable Roommates problem (sr) is a classical combinatorial problem that has been studied extensively in the literature [3,9,7,4,15,8]. An instance I of sr contains an undirected graph G=(A,E) where A={a1,...,an} and m=|E|. We assume that G contains no isolated vertices. We interchangeably refer to the vertices of G as the agents, and we refer to G as the underlying graph of I. (cid:2) PartofthisworkwasdonewhilstatDepartmentofComputingScience,University of Glasgow, and Max-Planck-Institutfu¨r Informatik. (cid:2)(cid:2) Partially supported by the Center for Applied Mathematics and Computational Physics, and by theHungarian National Science Fund(grant OTKA F 037301). (cid:2)(cid:2)(cid:2) Supported by the Engineering and Physical Sciences Research Council (grant GR/R84597/01), andbyRoyalSocietyofEdinburgh/ScottishExecutivePersonal Research Fellowship. T.ErlebachandG.Persiano(Eds.):WAOA2005,LNCS3879,pp.1–14,2006. (cid:1)c Springer-VerlagBerlinHeidelberg2006 2 D.J. Abraham,P. Bir´o, and D.F. Manlove The vertices adjacent to a given agent ai ∈ A are the acceptable agents for ai, denoted by Ai. If aj ∈ Ai, we say that ai finds aj acceptable. (Note that the acceptabilityrelationissymmetric,i.e.aj ∈Ai ifandonlyifai ∈Aj.)Moreover we assume that in I, ai has a linear order ≺ai over Ai, which we refer to as ai’s preference list. If aj ≺ai ak, we say that ai prefers aj to ak. Given aj ∈Ai, define rankai(aj)=1+|{ak ∈Ai :ak ≺ai aj}|. LetM beamatchinginI.If{ai,aj}∈M,wesaythataiismatched inM and M(ai)denotesaj,otherwiseai is unmatched inM.Ablocking pair withrespect to M is an edge {ai,aj} ∈ E\M such that (i) either ai is unmatched in M, or ai is matched in M and prefers aj to M(ai), and (ii) either aj is unmatched in M, or aj is matched in M and prefers ai to M(aj). Let bpI(M) denote the set of blocking pairs with respect to M in I (we omit the subscript if the instance is clear from the context). Matching M is stable in I if bpI(M)=∅. Gale and Shapley [3] showed that an instance of sr need not admit a stable matching(seeforexamplethesrinstanceIr inFigure1wherer=1).Irving[7] gaveanO(m)algorithmthatfindsastablematchingorreportsthatnoneexists, given an instance I of sr. The algorithmin [7] assumes that in I, all preference lists are complete (i.e. Ai =A\{ai} for each ai ∈A) and n is even, though it is straightforward to generalise the algorithm to the problem model defined here (i.e. the case of incomplete lists) [4]. Henceforth we denote by src the special case of sr in which all preference lists are complete. As the problem name suggests, an application of sr arises in the context of campus accommodation allocation, where we seek to assign students to share two-person rooms, based on their preferences over one another. Another appli- cationoccursinthecontextofformingpairingsofplayersforchesstournaments [10]. Very recently, a more serious application of sr has been studied, involving pairwise kidney exchange between incompatible patient-donor pairs [14]. Here, preferencelistscanbeconstructedonthebasisofcompatibilityprofilesbetween patients and potential donors. Empirical results [12] suggest that, as n increases, the probability that a random sr instance with n agents admits a stable matching decreases steeply. Equivalently,asngrowslarge,theseresultssuggestthatanarbitrarymatchingin arandomsr instance withn agentsis likelyto admitatleastoneblockingpair. In practical situations, a blocking pair {ai,aj} of a given matching M need not always lead to M being undermined by ai and aj, since these agents might not realise that together they block M. For example, in situations where preference lists are not public knowledge,there may be limited channels of communication that would lead to the awareness of blocking pairs in practice. Nevertheless, it is reasonable to assert that the greater the number of blocking pairs of a given matching M, the greater the likelihood that M would be undermined by a pair of agents in practice. Hence, given an sr instance that does not admit a stable matching, one may regard a matching that admits 1 blocking pair as being “morestable”thana matchingthatadmits 10blocking pairs,forexample.This motivatestheproblemoffinding,givenansrinstanceI withnostablematching,