Evripidis Bampis Ola Svensson (Eds.) 2 5 Approximation 9 8 S C and Online Algorithms N L 12th International Workshop, WAOA 2014 Wrocław, Poland, September 11–12, 2014 Revised Selected Papers 123 Lecture Notes in Computer Science 8952 Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen Editorial Board David Hutchison Lancaster University, Lancaster, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Friedemann Mattern ETH Zurich, Zürich, Switzerland John C. Mitchell Stanford University, Stanford, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen TU Dortmund University, Dortmund, Germany Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Gerhard Weikum Max Planck Institute for Informatics, Saarbrücken, Germany More information about this series at http://www.springer.com/series/7407 Evripidis Bampis Ola Svensson (Eds.) (cid:129) Approximation and Online Algorithms 12th International Workshop, WAOA 2014 ł – Wroc aw, Poland, September 11 12, 2014 Revised Selected Papers 123 Editors Evripidis Bampis OlaSvensson UniversitéPierre etMarie Curie, LIP6 EPFL-IC Paris Lausanne France Switzerland ISSN 0302-9743 ISSN 1611-3349 (electronic) Lecture Notesin Computer Science ISBN 978-3-319-18262-9 ISBN978-3-319-18263-6 (eBook) DOI 10.1007/978-3-319-18263-6 LibraryofCongressControlNumber:2015937010 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues SpringerChamHeidelbergNewYorkDordrechtLondon ©SpringerInternationalPublishingSwitzerland2015 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartofthe material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodologynow knownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbookare believedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsortheeditors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissionsthatmayhavebeenmade. Printedonacid-freepaper SpringerInternationalPublishingAGSwitzerlandispartofSpringerScience+BusinessMedia (www.springer.com) Preface The12thWorkshoponApproximationandOnlineAlgorithms(WAOA2014)focused onthedesignandanalysisofalgorithmsforonlineandcomputationallyhardproblems. Both kinds of problems have a large number of applications from a variety offields. WAOA 2014 took place in Wrocław, Poland, during September 11–12, 2014. The workshop was partoftheALGO 2014event thatalso hostedESA,ALGOSENSORS, ATMOS,IPEC,MASSIVE,andWABI.ThepreviousWAOAworkshopswereheldin Budapest(2003),Rome(2004),PalmadeMallorca(2005),Zurich(2006),Eilat(2007), Karlsruhe (2008), Copenhagen (2009), Liverpool (2010), Saarbrücken (2011), Ljubljana (2012), and Sophia Antipolis (2013). The proceedings of these previous WAOA workshops have appeared as LNCS volumes. Topics of interest for WAOA 2014 were: coloring and partitioning, competitive analysis, network design, packing and covering, paradigms for design and analysis of approximation and online algorithms, randomization techniques, real-world applica- tions, and scheduling problems. In response to the call for papers, we received 49 submissions.Eachsubmissionwasreviewedbyatleastthreereferees.Thesubmissions weremainlyjudgedonoriginality, technicalquality,andrelevancetothetopicsofthe conference. Based on the reviews, the Program Committee selected 22 papers. WearegratefultoAleksanderMadryforhisinvitedtalkandtoMonaldoMastrolilli for his tutorial. We would also like to thank Andrei Voronkov for providing the EasyChair conference system, which was used to manage the electronic submissions, the review process, and the electronic PC meeting. It made our task much easier. We wouldalsolike tothank alltheauthorswho submitted papers toWAOA 2014aswell as the local organizers of ALGO 2014. August 2014 Evripidis Bampis Ola Svensson Organization Program Committee Evripidis Bampis (Co-chair) Sorbonne Universités, Université Pierre et Marie Curie, France Nikhil Bansal Eindhoven University of Technology, The Netherlands Ioannis Caragiannis University of Patras, Greece Marek Chrobak University of California, Riverside, USA Alina R. Ene Princeton University, USA Moran Feldman EPFL, Switzerland Laurent Gourvès CNRS, Université Paris-Dauphine, France Nguyen Kim Thang Université d’Evry-Val-d’Essonne, France Alejandro López-Ortiz University of Waterloo, Canada Giorgio Lucarelli Sorbonne Universités, Université Pierre et Marie Curie, France Monaldo Mastrolilli IDSIA, Lugano, Switzerland Julian Mestre The University of Sydney, Australia Seffi Naor Technion, Israel Neil Olver CWI and VU University Amsterdam, The Netherlands Kirk Pruhs University of Pittsburgh, USA Thomas Rothvoss University of Washington, USA Laura Sanità University of Waterloo, Canada Ola Svensson (Co-chair) EPFL, Switzerland José Verschae Universidad de Chile, Chile Andreas Wiese Max-Planck-Institut für Informatik, Germany Invited Speaker Aleksander Madry EPFL, Switzerland Tutorial Monaldo Mastrolilli IDSIA, Switzerland VIII Organization Subreviewers Antonios Antoniadis Luigi Laura Ashwinkumar Badanidiyuru Julien Lesca Niv Buchbinder Dimitrios Letsios Martin Derka Shi Li Yann Disser Daniela Maftuleac Christoph Dürr Luke Mathieson Aristotelis Giannakos Ioannis Milis Michael Goldwasser Marco Molinaro Arpita Ghosh Jérôme Monnot Kiyohito Nagano Sandy Heydrich Viswanath Nagarajan Wiebke Höhn Krzysztof Onak Chien-Chung Huang Dror Rawitz Christian Icking Alejandro Salinger Sungjin Im Roy Schwartz Shahin Kamali Uwe Schwiegelshohn Panagiotis Kanellopoulos Matteo Seminaroti Hans Kellerer Florian Sikora Isaac Keslassy Lydia Tlilane Kim-Manuel Klein Erik Jan van Leeuwen Alexander Kononov David Wajc Maria Kyropoulou Justin Ward Adam Kurpisz Neal Young Contents Improved Approximations for the Max k-Colored Clustering Problem. . . . . . 1 Alexander Ageev and Alexander Kononov A oðnÞ-Competitive Deterministic Algorithm for Online Matching on a Line. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, and Michele Scquizzato Better Algorithms for Online Bin Stretching. . . . . . . . . . . . . . . . . . . . . . . . 23 Martin Böhm, Jiří Sgall, Rob van Stee, and Pavel Veselý Online Colored Bin Packing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Martin Böhm, Jiří Sgall, and Pavel Veselý Improved Bound for Online Square-into-Square Packing . . . . . . . . . . . . . . . 47 Brian Brubach Improved Approximation Algorithm for Fault-Tolerant Facility Placement. . . 59 Bartosz Rybicki and Jaroslaw Byrka The Submodular Facility Location Problem and the Submodular Joint Replenishment Problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Sin-Shuen Cheung Online Multi-Coloring with Advice. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Marie G. Christ, Lene M. Favrholdt, and Kim S. Larsen Approximating Steiner Trees and Forests with Minimum Number of Steiner Points. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Nachshon Cohen and Zeev Nutov Energy-Efficient Algorithms for Non-preemptive Speed-Scaling . . . . . . . . . . 107 Vincent Cohen-Addad, Zhentao Li, Claire Mathieu, and Ioannis Milis Optimal Online and Offline Algorithms for Robot-Assisted Restoration of Barrier Coverage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 J. Czyzowicz, E. Kranakis, D. Krizanc, L. Narayanan, and J. Opatrny Linear-Time Approximation Algorithms for Unit Disk Graphs . . . . . . . . . . . 132 Guilherme D. da Fonseca, Vinícius G. Pereira de Sá, and Celina M.H. de Figueiredo X Contents The Minimum Feasible Tileset Problem. . . . . . . . . . . . . . . . . . . . . . . . . . . 144 Yann Disser, Stefan Kratsch, and Manuel Sorge Online Ad Assignment with an Ad Exchange. . . . . . . . . . . . . . . . . . . . . . . 156 Wolfgang Dvořák and Monika Henzinger Minimum Linear Arrangement of Series-Parallel Graphs . . . . . . . . . . . . . . . 168 Martina Eikel, Christian Scheideler, and Alexander Setzer Online Dual Edge Coloring of Paths and Trees. . . . . . . . . . . . . . . . . . . . . . 181 Lene M. Favrholdt and Jesper W. Mikkelsen Online Packet Scheduling Under Adversarial Jamming . . . . . . . . . . . . . . . . 193 Tomasz Jurdzinski, Dariusz R. Kowalski, and Krzysztof Lorys Generalized Hypergraph Matching via Iterated Packing and Local Ratio . . . . 207 Ojas Parekh and David Pritchard Steiner Trees with Bounded RC-Delay. . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 Rudolf Scheifele Multiprocessor Jobs, Preemptive Schedules, and One-Competitive Online Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 Jiří Sgall and Gerhard J. Woeginger Routing Under Uncertainty: The a priori Traveling Repairman Problem . . . . 248 Martijn van Ee and René Sitters Primal-Dual Algorithms for Precedence Constrained Covering Problems . . . . 260 Andreas Wierz, Britta Peis, and S. Thomas McCormick Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273