Lecture Notes in Computer Science 5893 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA AlfredKobsa UniversityofCalifornia,Irvine,CA,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen TUDortmundUniversity,Germany MadhuSudan MicrosoftResearch,Cambridge,MA,USA DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA GerhardWeikum Max-PlanckInstituteofComputerScience,Saarbruecken,Germany Evripidis Bampis Klaus Jansen (Eds.) Approximation and Online Algorithms 7th International Workshop,WAOA 2009 Copenhagen, Denmark, September 10-11, 2009 Revised Papers 1 3 VolumeEditors EvripidisBampis Universitéd’EvryVald’Essonne,IBISC,CNRSFRE3190 PlacedesTerasses,TourEvry2,91000EvryCedex,France E-mail:[email protected] KlausJansen UniversitätKiel,InstitutfürInformatik Olshausenstr.40,24098Kiel,Germany E-mail:[email protected] LibraryofCongressControlNumber:2010924119 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-642-12449-6SpringerBerlinHeidelbergNewYork ISBN-13 978-3-642-12449-5SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. springer.com ©Springer-VerlagBerlinHeidelberg2010 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper 06/3180 Preface The 7th Workshop on Approximation and Online Algorithms (WAOA 2009) focused on the design and analysis of algorithms for online and computation- ally hardproblems. Bothkinds of problems have a largenumber of applications from a variety of fields. WAOA 2009 took place in Copenhagen, Denmark, dur- ing September 10–11, 2009. The workshop was part of the ALGO 2009 event that also hosted ESA 2009, IWPEC 2009, and ATMOS 2009. The previous WAOA workshops were held in Budapest (2003), Rome (2004), Palma de Mal- lorca(2005),Zurich(2006),Eilat(2007),andKarlsruhe(2008).Theproceedings ofthesepreviousWAOAworkshopshaveappearedasLNCSvolumes2909,3351, 3879, 4368,4927, and 5426,respectively. Topics of interest for WAOA 2009 were: algorithmic game theory, approx- imation classes, coloring and partitioning, competitive analysis, computational finance, cuts and connectivity, geometric problems, inapproximability results, mechanism design, network design, packing and covering, paradigms for design andanalysisofapproximationandonlinealgorithms,parameterizedcomplexity, randomization techniques, real-world applications, and scheduling problems. In response to the call for papers, we received 62 submissions. Each submis- sionwasreviewedbyatleastthreereferees,andthevastmajoritybyatleastfour referees. The submissions were mainly judged on originality, technical quality, andrelevancetothetopicsoftheconference.Basedonthereviews,theProgram Committee selected 22 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 2009 as well as the local organizers of ALGO 2009. December 2009 Evripidis Bampis Klaus Jansen Organization Program Co-chairs Evripidis Bampis University of Evry, France Klaus Jansen University of Kiel, Germany Program Committee Vincenzo Auletta University of Salerno, Italy Evripidis Bampis University of Evry, France Nikhil Bansal IBM T.J. Research Center Watson, USA Constantinos Daskalakis Microsoft Research and MIT, USA Christoph Durr CNRS, Ecole Polytechnique, France Friedrich Eisenbrand EPFL Lausanne, Switzerland Thomas Erlebach University of Leicester, UK Klaus Jansen University of Kiel, Germany Christos Kaklamanis University of Patras,Greece Sanjeev Khanna University of Pennsylvania, USA Monaldo Mastrolilli IDSIA Lugano, Switzerland Yuval Rabani Technion Haifa, Israel Nicolas Schabanel CNRS, University Paris Diderot, France Roberto Solis-Oba University of Western Ontario, Canada Neal Young University of California Riverside, USA Guochuan Zhang Zhejiang University Hangzhou, China Referees Susanne Albers Hiroshi Fujiwara Eric Angel Stefan Funke Elliot Anshelevich Mira Gonen Yossi Azar laurent gourv`es Marin Bougeret Fabrizio Grandoni Andreas Brandsta¨dt Danny Hermelin Jaros(cid:2)law Byrka Tobias Jacobs Ioannis Caragiannis Panagiotis Kanellopoulos Lin Chen Jochen Ko¨nemann Marek Chrobak Elias Koutsoupias Michael Elkin So¨ren Laue Diodato Ferraioli Van Bang Le Dimitris Fotakis Daniel Lokshtanov Pierre Fraigniaud Bin Lu VIII Organization Shuang Luan Eric Remila Pa´ll Melsted Thomas Rothvoss Julian Mestre Heiko R¨oglin Ioannis Milis Laura Sanita` J´erˆome monnot Ulrich M. Schwarz Hannes Moser Danny Segev Nikolaus Mutsanas Bruce Shepherd Tim Nonner Gregory Valiant Christina Otte Carmine Ventre Konstantinos Panagiotou Andreas Wiese Evi Papaioannou Prudence W.H. Wong Fanny Pascual Haifeng Xu Ulrich Pferschy Deshi Ye Lars Pra¨del Vassilis Zissimopoulos Do¨m¨oto¨r Pa´lvo¨lgyi Table of Contents WAOA 2009 On the Competitiveness of the Online Asymmetric and Euclidean Steiner Tree Problems ............................................ 1 Spyros Angelopoulos Extension of the Nemhauser and Trotter Theorem to Generalized Vertex Cover with Applications.................................... 13 Reuven Bar-Yehuda, Danny Hermelin, and Dror Rawitz Price Fluctuations: To Buy or to Rent.............................. 25 Marcin Bienkowski Approximation Algorithms for Multiple Strip Packing ................ 37 Marin Bougeret, Pierre Francois Dutot, Klaus Jansen, Christina Otte, and Denis Trystram Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window.................................................. 49 Ho-Leung Chan, Tak-Wah Lam, Lap-Kei Lee, and Hing-Fung Ting Longest Wait First for Broadcast Scheduling (Extended Abstract)...... 62 Chandra Chekuri, Sungjin Im, and Benjamin Moseley The Routing Open Shop Problem: New Approximation Algorithms..... 75 Ilya Chernykh, Nikita Dryuck, Alexander Kononov, and Sergey Sevastyanov On the Price of Stability for Undirected Network Design .............. 86 George Christodoulou, Christine Chung, Katrina Ligett, Evangelia Pyrga, and Rob van Stee Finding Dense Subgraphs in G(n,1/2).............................. 98 Atish Das Sarma, Amit Deshpande, and Ravi Kannan ParameterizedAnalysis of Paging and List Update Algorithms......... 104 Reza Dorrigiv, Martin R. Ehmsen, and Alejandro Lo´pez-Ortiz Online Scheduling of Bounded Length Jobs to Maximize Throughput... 116 Christoph Du¨rr, L(cid:2)ukasz Jez˙, and Kim Thang Nguyen On the Additive Constant of the k-Server Work Function Algorithm.... 128 Yuval Emek, Pierre Fraigniaud, Amos Korman, and Adi Ros´en X Table of Contents A (4+(cid:2))-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs...................................... 135 Thomas Erlebach and Matu´ˇs Mihala´k Guard Games on Graphs: Keep the Intruder Out!.................... 147 Fedor V. Fomin, Petr A. Golovach, and Daniel Lokshtanov Between a Rock and a Hard Place: The Two-to-One Assignment Problem ........................................................ 159 Dries Goossens, Sergey Polyakovskiy, Frits C.R. Spieksma, and Gerhard J. Woeginger Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width ............................................... 170 Elisabeth Gu¨nther, Felix G. Ko¨nig, and Nicole Megow Online Minimization Knapsack Problem ............................ 182 Xin Han and Kazuhisa Makino Optimization Problems in Multiple Subtree Graphs .................. 194 Danny Hermelin and Dror Rawitz Multi-Criteria TSP: Min and Max Combined ........................ 205 Bodo Manthey Packet Routing: Complexity and Algorithms ........................ 217 Britta Peis, Martin Skutella, and Andreas Wiese Minimal Cost Reconfiguration of Data Placement in Storage Area Network ........................................................ 229 Hadas Shachnai, Gal Tamir, and Tami Tamir Competitive Multi-dimensional Dynamic Bin Packing via L-Shape Bin Packing......................................................... 242 Prudence W.H. Wong and Fencol C.C. Yung Author Index.................................................. 255 On the Competitiveness of the Online Asymmetric and Euclidean Steiner Tree Problems Spyros Angelopoulos Max-Planck-Institut fu¨r Informatik Saarbru¨cken 66123, Germany Abstract. Thispaperaddressesthecompetitivenessofonlinealgorithms fortwoSteinerTreeproblems.Inthefirstproblem,theunderlyinggraph isdirectedandhasboundedasymmetry,namelythemaximumweightof antiparallel links in the graph does not exceed a parameter α. Previous work onthisproblem hasleft agap on thecompetitiveratio whichisas largeaslogarithmicink.Wepresentarefinedanalysis,bothintermsof the upper and the lower bounds, that closes the gap and shows that a greedy algorithm is optimal for all valuesof theparameter α. The second part of the paper addresses the Euclidean Steiner tree problem on the plane. Alon and Azar [SoCG 1992, Disc. Comp. Geom. 1993]gaveanelegantlowerboundonthecompetitiveratioofanydeter- ministic algorithm equal to Ω(logk/loglogk); however, thebest known upperboundisthetrivialboundO(logk).Wegivethefirstanalysisthat makesprogress towardsclosingthislong-standinggap.Inparticular,we present an online algorithm with competitive ratio O(logk/loglogk), provided that the optimal offline Steiner tree belongs in a class of trees with relatively simple structure. This class comprises not only the ad- versarialinstancesofAlonandAzar,butalsoallrectilinearSteinertrees whichcanbedecomposedinapolylogarithmicnumberofrectilinearfull Steiner trees. 1 Introduction Problem statements and motivation The Steiner treeproblemoccupiesacentral place in combinatorial optimization, and has been studied extensively under many variants. The standard setting involves an underlying graph G = (V,E), with a non-negative weight function c : E → R+ over its edges (which reflects thecostoftheedge).GivenasubsetK ⊆V ofverticesalsocalledterminals,the objective is to find a tree of minimum cost that spans all vertices in K. Here, the cost of the tree is defined as the sum of the cost of all the edges in the tree. In this paper we focus on the following Steiner tree problems. • IntheasymmetricSteinertreeproblem,theunderlyinggraphisdirected,and a specific vertex r ∈ V is designated as the root. We define the asymmetry α of graph G as the maximum ratio of the cost of antiparallel links in G. More E.BampisandK.Jansen(Eds.):WAOA2009,LNCS5893,pp.1–12,2010. (cid:2)c Springer-VerlagBerlinHeidelberg2010