ALGO 2012 schedule

18:00 – 19:00

Welcome reception

08:45 – 09:00	Opening ESA & WABI – White Hall
09:00 – 10:00	Plenary – White Hall Yossi Matias: On Big Data Algorithmics Chair: Paolo Ferragina (ESA)
10:00 – 10:30	coffee break
	ESA I – White Hall Chair: Asaf Levin Approximation algorithms	ESA II – Glass Hall 2+3 Chair: Jens Stoye Graph algorithms	WABI – Glass Hall 1 Chair: Matthias Bernt Phylogenetic Trees 1	WABI – Blue Hall
10:30 – 10:55	Marek Cygan, Guy Kortsarz and Zeev Nutov. Steiner Forest Orientation Problems	Daniel Delling and Renato Werneck. Better Bounds for Graph Bisection	Matthias Bernt, Kun-Mao Chao, Jyun-Wei Kao, Martin Middendorf and Eric Tannier. Preserving Inversion Phylogeny Reconstruction	WABI poster session
10:55 – 11:20	Manisha Bansal, Naveen Garg and Neelima Gupta. A 5-approximation for capacitated facility location	Ittai Abraham, Daniel Delling, Andrew Goldberg and Renato Werneck. Hierarchical Hub Labelings for Shortest Paths	Daniel G. Brown and Jakub Truszkowski. Fast Phylogenetic Tree Reconstruction Using Locality-Sensitive Hashing
11:20 – 11:45	Pavol Hell, Monaldo Mastrolilli, Mayssam Nevisi and Arash Rafiey. Approximation of Minimum Cost Homomorphisms	Deepak Ajwani, Ulrich Meyer and David Veith. I/O-efficient hierarchical diameter approximation	Constantinos Tsirogiannis, Brody Sandel and Dimitris Cheliotis. Efficient Computation of Popular Phylogenetic Tree Measures
11:45 – 12:10	Martin Groß and Martin Skutella. Maximum Multicommodity Flows Over Time without Intermediate Storage	Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura and Federico Santaroni. An Experimental Study of Dynamic Dominators	Rob Gysel, Kristian Stevens and Dan Gusfield. Reducing Problems in Unrooted Tree Compatibility to Restricted Triangulations of Intersection Graphs
12:10 – 13:30	lunch
	ESA I – White Hall Chair: Matthias Mnich Graph classes	ESA II – Glass Hall 2+3 Chair: Chien-Chung Huang Network optimization	WABI – Glass Hall 1 Chair: Jens Stoye Genetics
13:30 – 13:55	Sergio Cabello, Jean Cardinal and Stefan Langerman. The Clique Problem in Ray Intersection Graphs	Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Pilipczuk and Piotr Sankowski. A Path-Decomposition Theorem with Applications to Pricing and Covering on Trees	Daniel G. Brown and Daniel Dexter. SibJoin: A Fast Heuristic for Half-Sibling Reconstruction
13:55 – 14:20	Josep Diaz, Olli Pottonen, Maria Serna and Erik Jan van Leeuwen. On the Complexity of Metric Dimension	Debojyoti Dutta, Michael Kapralov, Ian Post and Rajendra Shinde. Embedding paths into trees: VM placement to minimize congestion	Bjarni V. Halldórsson, Dima Blokh and Roded Sharan. Estimating Population Size via Line Graph Reconstruction
14:20 – 14:45	Dieter Kratsch and Haiko Muller. Colouring AT-free graphs	Shiri Chechik. Improved Distance Oracles and Spanners for Vertex-Labeled Graphs	Yen-Yi Lin, Phuong Dao, Faraz Hach, Marzieh Bakhshi, Fan Mo, Anna Lapuk, Colin Collins and S. Cenk Sahinalp. CLIIQ: Accurate Comparative Detection and Quantification of Expressed Isoforms in a Population
14:45 – 15:15	coffee break
	ESA I – White Hall Chair: Hans Bodlaender Graph algorithms	ESA II – Glass Hall 2+3 Chair: Mark de Berg Distances	WABI – Glass Hall 1 Chair: Daniel G. Brown Networks
15:15 – 15:40	Pavel Klavik, Jan Kratochvil, Tomasz Krawczyk and Bartosz Walczak. Extending partial representations of function graphs and permutation graphs	Laszlo Kozma. Minimum Average Distance Triangulations	Yi Shi, Xiaoping Liao, Xinhua Zhang, Guohui Lin and Dale Schuurmans. Sparse Learning Based Linear Coherent Bi-clustering
15:40 – 16:05	Jan Arne Telle and Yngve Villanger. FPT algorithms for domination in biclique-free graphs	Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse and Ljubomir Perkovic. The Stretch Factor of $L_1$- and $L_\infty$-Delaunay Triangulations	Anirban Bhar, Martin Haubrock, Anirban Mukhopadhyay Ujjwal Maulik, Sanghamitra Bandyopadhyay and Edgar Wingender. δ-TRIMAX: Extracting Triclusters and Analysing Coregulation in Time Series Gene Expression Data
16:05 – 16:30	Danny Hermelin, Matthias Mnich and Erik Jan van Leeuwen. Parameterized Complexity of Induced H-Matching on Claw-Free Graphs	Hossein Jowhari. Efficient Communication Protocols for Deciding Edit Distance	Shay Houri and Roded Sharan. Sign Assignment Problems on Protein Networks
16:30 – 17:00	coffee break
	ESA I – White Hall Chair: Danny Hermelin Fixed Parameter Tractability	ESA II – Glass Hall 2+3 Chair: Danny Halperin Computational Geometry	WABI – Glass Hall 1 Chair: Yi Shi Network, RNA sequence and structure
17:00 – 17:25	Petr Golovach, Daniel Paulusma and Erik Jan van Leeuwen. Induced Disjoint Paths in Claw-Free Graphs	Mark De Berg, Marcel Roeloffzen and Bettina Speckmann. Kinetic Compressed Quadtrees in the Black-Box Model with Applications to Collision Detection for Low-Density Scenes	Nimrod Milo, Shay Zakov, Erez Katzenelson, Eitan Bachmat, Yefim Dinitz and Michal Ziv-Ukelson. RNA Tree Comparisons via Unrooted Unordered Alignments
17:25 – 17:50	Fedor Fomin, Saket Saurabh and Yngve Villanger. A Polynomial kernel for Proper Interval Vertex Deletion	A. Karim Abu-Affash, Paz Carmi, Matthew Katz and Yohai Trabelsi. Bottleneck Non-Crossing Matching in the Plane	Philippe Rinaudo, Yann Ponty, Dominique Barth and Alain Denise. Tree Decomposition and Parameterized Algorithms for RNA Structure-Sequence Alignment Including Tertiary Interactions and Pseudoknots
17:50 – 18:15	Yasuaki Kobayashi and Hisao Tamaki. A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization	Kevin Buchin, Maike Buchin, Wouter Meulemans and Bettina Speckmann. Locally Correct Fre'chet Matchings	Yun Zhu and Luay Nakhleh. Reconstructing the Evolution of Molecular Interaction Networks under the DMC and Link Dynamics Models
18:30 – 19:30	ESA – White Hall business meeting		WABI – Glass Hall 1 business meeting

09:00 – 10:00	Plenary – White Hall Jens Stoye: Algorithms for Genome Rearrangement by Double Cut and Join Chair: Jijun Tang (WABI)
10:00 – 10:30	coffee break
	ESA I – White Hall Chair: Rob van Stee Algorithmic Game Theory 1	ESA II – Glass Hall 2+3 Chair: Alejandro López-Ortiz Networks and Maps	WABI – Glass Hall 1 Chair: Luay Nakhleh Genome Rearrangements	WABI – Blue Hall
10:30 – 10:55	Tobias Harks and Britta Peis. Resource Buying Games	Gernot Veit Batz and Peter Sanders. Time-Dependent Route Planning with Generalized Objective Functions	Phillip E.C. Compeau. A Simplified View of DCJ-Indel Distance	WABI poster session
10:55 – 11:20	Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger and Danupon Nanongkai. Polynomial-time Algorithms for Energy Games with Special Weight Structures	Mahmuda Ahmed and Carola Wenk. Constructing Street Networks from GPS Trajectories	Poly H. da Silva, Marília D.V. Braga, Raphael Machado and Simone Dantas. DCJ-indel Distance with Distinct Operation Costs
11:20 – 11:45	Bart De Keijzer and Guido Schaefer. Finding Social Optima in Congestion Games with Positive Externalities	Lars Arge, Lasse Deleuran, Thomas Mølhave, Morten Revsbæk, and Jakob Truelsen. Simplifying Massive Contour Maps	Birte Kehr, Knut Reinert and Aaron E. Darling. Hidden Breakpoints in Genome Alignments
11:45 – 12:10	Rasmus Ibsen-Jensen and Peter Bro Miltersen. Solving simple stochastic games with few coin toss positions	Martin Waßmann and Karsten Weicker. Maximum Flow Networks for Stability Analysis of LEGO Structures	Antoine Thomas, Aïda Ouangraoua and Jean-Stéphane Varré. Tandem Halving Problems by DCJ
12:10 – 13:30	lunch
	ESA I – White Hall Chair: Leah Epstein and Paolo Ferragina Best papers session		WABI – Glass Hall 1 Chair: Giovanna Rosone DNA Sequencing and Assembly 1
13:30 – 13:55	Martin Gross, Jan-Philipp W. Kappmeier, Daniel R. Schmidt and Melanie Schmidt. Approximating Earliest Arrival Flows in Arbitrary Networks (student best paper)		Alexander Bowe, Taku Onodera, Kunihiko Sadakane and Tetsuo Shibuya. Succinct de Bruijn Graphs
13:55 – 14:20	Sebastian Wild and Markus E. Nebel. Average Case Analysis of Java 7's Dual Pivot Quicksort		Rayan Chikhi and Guillaume Rizk. Space-Efficient and Exact de Bruijn Graph Representation Based on a Bloom Filter
14:20 – 14:45	Clément Maria and Jean-Daniel Boissonnat. The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes		Nikolay Vyahhi, Alex Pyshkin, Son Pham and Pavel A. Pevzner. From de Bruijn Graphs to Rectangle Graphs for Genome Assembly
14:45 – 15:15	coffee break
	ESA I – White Hall Chair: Kirk Pruhs Algorithmic Game Theory 2	ESA II – Glass Hall 2+3 Chair: Pinar Heggernes Networks	WABI – Glass Hall 1 Chair: Kira Vyatkina DNA Sequencing and Assembly 2
15:15 – 15:40	T-H. Hubert Chan, Fei Chen and Li Ning. Optimizing Social Welfare for Network Bargaining Games in the Face of Unstability, Greed and Spite	Emanuele Guido Fusco and Andrzej Pelc. Knowledge, Level of Symmetry, and Time of Leader Election	Olga Tanaseichuk, James Borneman and Tao Jiang. A Probabilistic Approach to Accurate Abundance-Based Binning of Metagenomic Reads
15:40 – 16:05	Fidaa Abed and Chien-Chung Huang. Preemptive Coordination Mechanisms for Unrelated Machines	Bundit Laekhanukit, Adrian Vetta and Gordon Wilfong. Routing Regardless of Network Stability	Song Gao, Denis Bertrand and Niranjan Nagarajan. FinIS: Improved in silico Finishing Using an Exact Quadratic Programming Formulation
16:05 – 16:30	Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos and Maria Kyropoulou. Revenue guarantees in sponsored search auctions	Frank Hellweg and Christian Sohler. Property Testing in Sparse Directed Graphs: Strong Connectivity and Subgraph-Freeness	Markus J. Bauer, Anthony J. Cox, Giovanna Rosone and Marinella Sciortino. Lightweight LCP Construction for Next-Generation Sequencing Datasets
16:30 – 23:00	excursion and conference dinner

08:45 – 09:00	Opening IPEC – White Hall
09:00 – 10:00	Plenary – White Hall Jiří Sgall: Open Problems in Throughput Scheduling Chair: Leah Epstein (ESA)
10:00 – 10:30	coffee break
	ESA I – White Hall Chair: Jiří Sgall Scheduling	ESA II – Glass Hall 2+3 Chair: Rajeev Raman Computational Geometry	WABI – Glass Hall 1 Chair: David Fernandez-Baca Protein Sequence and Structure	IPEC – Red Hall Chair: Fedor V. Fomin IPEC 1	WABI – Blue Hall
10:30 – 10:55	Siddharth Barman, Shuchi Chawla and Seeun Umboh. A Bicriteria Approximation for the Reordering Buffer Problem	Vissarion Fisikopoulos and Luis Peñaranda. Faster Geometric Algorithms via Dynamic Determinant Computation	Natalie E. Castellana, Andrey Lushnikov, Piotr Rotkiewicz, Natasha Sefcovic, Pavel A. Pevzner, Adam Godzik and Kira Vyatkina. MORPH-PRO: A Novel Algorithm and Web Server for Protein Morphing	Marcin Pilipczuk and Michał Pilipczuk. Finding a maximum induced degenerate subgraph faster than 2^n	WABI poster session
10:55 – 11:20	Jessica Chang, Harold Gabow and Samir Khuller. A Model for Minimizing Active Processor Time	Michael Hemmer, Michal Kleinbort and Dan Halperin. Improved Implementation of Point Location in General Two-Dimensional Subdivisions	Xuefeng Cui, Shuai Cheng Li, Dongbo Bu, Babak Alipanahi Ramandi and Ming Li. How Accurately Can We Model Protein Structures with Dihedral Angles?	Chiranjit Chakraborty and Rahul Santhanam. Instance Compression for the Polynomial Hierarchy and Beyond
11:20 – 11:45	Susanne Albers and Matthias Hellwig. On the Value of Job Migration in Online Makespan Minimization	Peter Palfrader, Martin Held and Stefan Huber. On Computing Straight Skeletons by Means of Kinetic Triangulations	Geet Duggal, Rob Patro, Emre Sefer, Hao Wang, Darya Filippova, Samir Khuller and Carl Kingsford. Resolving Spatial Inconsistencies in Chromosome Conformation Data	Ivan Bliznets and Alexander Golovnev. A New Algorithm for Parameterized MAX-SAT
11:45 – 12:10	Thomas Kesselheim. Approximation Algorithms for Wireless Link Scheduling with Flexible Data Rates	Efi Fogel, Michael Hemmer, Asaf Porat and Dan Halperin. Lines Through Segments in 3D Space	Hosein Mohimani, Sangtae Kim and Pavel A. Pevzner. MS-DPR: An Algorithm for Computing Statistical Significance of Spectral Identifications of Non-linear Peptides
12:10 – 13:30	lunch
	ESA I – White Hall Chair: Andrej Brodnik Data structures 1	ESA II – Glass Hall 2+3 Chair: Vincenzo Bonifaci Approximation algorithms for graphs	WABI – Glass Hall 1 Chair: Leo van Iersel Phylogenetic Trees 2	IPEC – Red Hall Chair: Dimitrios M. Thilikos Tutorial
13:30 – 13:55	Martin Aumüller, Martin Dietzfelbinger and Philipp Woelfel. Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash	James Davis and David Williamson. A Dual-Fitting 3/2-Approximation Algorithm for Some Minimum-Cost Graph Problems	Manuel Lafond, Krister M. Swenson and Nadia El-Mabrouk. An Optimal Reconciliation Algorithm for Gene Trees with Polytomies	Saket Saurabh. Subexponential Parameterised Algorithms
13:55 – 14:20	J. Ian Munro and Patrick K. Nicholson. Succinct Posets	Jose A. Soto, Jose R. Correa and Omar Larre. TSP tours in Cubic Graphs: Beyond 4/3	Thi Hau Nguyen, Jean-Philippe Doyon, Stéphanie Pointet, Anne-Muriel Arigon Chifolleau, Vincent Ranwez and Vincent Berry. Accounting for Gene Tree Uncertainties Improves Gene Trees and Reconciliation Inference
14:20 – 14:45	Martin Babka, Jan Bulánek, Michal Koucký, Vladimír Čunát and Michael Saks. On online labeling with polynomially many labels	Fabrizio Grandoni. On Min-Power Steiner Tree	Akshay Deepak, David Fernández-Baca and Michelle M. McMahon. Extracting Conflict-Free Information from Multi-labeled Trees
14:45 – 15:15	coffee break
	ESA I – White Hall Chair: Alejandro López-Ortiz Data structures 2	ESA II – Glass Hall 2+3 Chair: Samir Khuller Optimization	WABI – Glass Hall 1 Chair: Rayan Chikhi Tree Analysis	IPEC – Red Hall Chair: Michał Pilipczuk IPEC 2
15:15 – 15:40	Eunhui Park and David Mount. A Self-Adjusting Data Structure for Multidimensional Point Sets	Tim Nonner. Polynomial-Time Approximation Schemes for Shortest Path with Alternatives	Leo van Iersel, Steven Kelk, Nela Lekić and Celine Scornavacca. A Practical Approximation Algorithm for Solving Massive Instances of Hybridization Number	Bruno Escoffier, Jérôme Monnot, Vangelis Paschos and Mingyu Xiao. New results on polynomial inapproximability and fixed parameter approximability of EDGE DOMINATING SET
15:40 – 16:05	Bernard Chazelle and Wolfgang Mulzer. Data Structures on Event Graphs	Joachim Giesen, Martin Jaggi and Soeren Laue. Optimizing over the Growing Spectrahedron	Yasuo Tabei. Succinct Multibit Tree: Compact Representation of Multibit Trees by Using Succinct Data Structures in Chemical Fingerprint Searches	Paola Bonizzoni, Riccardo Dondi, Giancarlo Mauri and Italo Zoppis. Restricted and Swap Common Superstring: a Parameterized View
16:05 – 16:30	Meng He, Ian Munro and Gelin Zhou. Succinct Data Structures for Path Queries	Nikhil Bansal and Kirk Pruhs. Weighted Geometric Set Multi-cover via Quasi-Uniform Sampling	Brad Shutters, Sudheer Vakati, and David Fernández-Baca. Improved Lower Bounds on the Compatibility of Quartets, Triplets, and Multi-state Characters	Łukasz Kowalik. Nonblocker in H-minor free graphs: kernelization meets discharging
16:30 – 17:00	coffee break
	ESA I – White Hall Chair: Ian Munro Data structures 3	ESA II – Glass Hall 2+3 Chair: Michal Koucky Theory of computing	WABI – Glass Hall 1 Chair: Jijun Tang Sequence Analysis	IPEC – Red Hall Chair: Dániel Marx IPEC 3
17:00 – 17:25	Peyman Afshani and Norbert Zeh. Sorted Geometric Queries Require Superlinear Space	Aleksandrs Belovs and Ben Reichardt. Span programs and quantum algorithms for st-connectivity and claw detection	Anthony J. Cox, Tobias Jakobi, Giovanna Rosone, and Ole B. Schulz-Trieglaff. Comparing DNA Sequence Collections by Direct Comparison of Compressed Text Indexes	Faisal Abu-Khzam and Mazen Bu Khuzam. An Improved Kernel for the Undirected Planar Feedback Vertex Set Problem
17:25 – 17:50	Gerth Brodal, Pooya Davoodi, Moshe Lewenstein, Rajeev Raman and Srinivasa Rao Satti. Two Dimensional Range Minimum Queries and Fibonacci Lattices	Andrew Childs, Shelby Kimmel and Robin Kothari. The quantum query complexity of read-many formulas	Niko Välimäki and Simon J. Puglisi. Distributed String Mining for High-Throughput Sequencing Data	Petr A. Golovach, Pinar Heggernes, Dieter Kratsch and Reza Saei. An exact algorithm for Subset Feedback Vertex Set on chordal graphs
17:50 – 18:15	Djamal Belazzougui and Gonzalo Navarro. New Lower and Upper Bounds for Representing Sequences	T-H. Hubert Chan, Elaine Shi and Dawn Song. Optimal Lower Bound for Differentially Private Multi-Party Aggregation		Cédric Bentz. A polynomial-time algorithm for planar multicuts with few source-sink pairs

08:45 – 09:00	Opening ALGOSENSORS, WAOA, MASSIVE & ATMOS – Orchid Hall
09:00 – 10:00	Plenary – Orchid Hall Dániel Marx: Randomized techniques for parameterized algorithms Chair: Dimitrios M. Thilikos (IPEC)
10:00 – 10:30	coffee break
	IPEC – Red Hall Chair: Faisal Abu-Khzam IPEC 4	ATMOS – Iris Hall Chair: Daniel Delling Assignment and Traffic Management	ALGOSENSORS – Rose Hall Chair: Magnús M. Halldórsson SINR Model	WAOA – Orchid Hall Chair: Thomas Erlebach Graphs and Networks	MASSIVE – Silver Hall Chair: Alejandro López-Ortiz MASSIVE 1
10:30 – 10:55	Fedor V. Fomin, Bart Jansen and Michał Pilipczuk. Preprocessing Subgraph and Minor Problems: When Does a Small Vertex Cover Help?	Valentina Cacchiani, Alberto Caprara and Paolo Toth. A Fast Heuristic Algorithm for the Train Unit Assignment Problem	Thomas Kesselheim. Approximation Algorithms for Wireless Spectrum Allocation with Power Control	Stefan Dobrev, Rastislav Královič and Richard Královič. Independent Set with Advice: The Impact of Graph Knowledge	Jan Bulánek, Michal Koucký and Michael Saks. The online labeling problem
10:55 – 11:20	Yijia Chen, Kord Eickmeyer and Jörg Flum. The exponential time hypothesis and the parameterized clique problem	Markus Bohlin, Florian Dahms, Holger Flier and Sara Gestrelius. Optimal Freight Train Classification using Column Generation		Guy Even and Moti Medina. Online Multi-Commodity Flow with High Demands	Lars Arge, Michael Goodrich and Freek van Walderveen. Computing Betweenness Centrality in External Memory
11:20 – 11:45	Abhijin Adiga, Jasine Babu and L. Sunil Chandran. Polynomial Time and Parameterized Approximation Algorithms for Boxicity	Paola Pellegrini, Grégory Marlière and Joaquin Rodriguez. Real time railway traffic management modeling track-circuits	Tigran Tonoyan. On Some Bounds on the Optimum Schedule Length in the SINR Model	Markus Chimani and Joachim Spoerhase. Approximating Spanning Trees with Few Branches	Tetsuo Asano, Maike Buchin, Kevin Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote and André Schulz. Memory-Constrained Algorithms for Simple Polygons.
11:45 – 12:10		Mohammad Hossein Keyhani, Mathias Schnee, Karsten Weihe and Hans-Peter Zorn. Reliability and Delay Distributions of Train Connections	Lukas Belke, Thomas Kesselheim, Arie Koster and Berthold Voecking. Comparative Study of Approximation Algorithms and Heuristics for SINR Scheduling with Power Control	Itamar Hartstein, Mordechai Shalom and Shmuel Zaks. On the Complexity of the Regenerator Location Problem - Treewidth and Other Parameters	Gerth Stølting Brodal, Spyros Sioutas, Konstantinos Tsakalidis and Kostas Tsichlas. Fully Persistent B-Trees
12:10 – 13:30	lunch
13:30 – 14:30	Plenary – Orchid Hall Matthias Müller-Hannemann: Algorithm Engineering of Timetable Information Chair: Daniel Delling (ATMOS)
14:30 – 15:00	coffee break
	IPEC – Red Hall Chair: Saket Saurabh Tutorial	ATMOS – Iris Hall Chair: Renato Werneck Routing	ALGOSENSORS – Rose Hall Chair: Nikhil Bansal Ad Hoc Networks	WAOA – Orchid Hall Chair: Wolfgang Bein Geometric Problems	MASSIVE – Silver Hall Chair: Gerth Stølting Brodal MASSIVE 2
15:00 – 15:25	Michał Pilipczuk. Lower bounds for polynomial kernelization	Ralf Borndörfer and Marika Karbstein. A Direct Connection Approach to Integrated Line Planning and Passenger Routing	Shaun Joseph and Lisa Dipippo. Pseudo-scheduling: A New Approach to the Broadcast Scheduling Problem	Robert Georges, Frank Hoffmann and Klaus Kriegel. Online Exploration of Polygons with Holes	Giorgio Ausiello, Donatella Firmani, Luigi Laura and Emanuele Paracone. Large-Scale Graph Biconnectivity in MapReduce
15:25 – 15:50		Felix G. König, Jannik Matuschke and Alexander Richter. Multi-dimensional commodity covering for tariff selection in transportation	Jinhee Chun, Akiyoshi Shioura, Truong Minh Tien and Takeshi Tokuyama. A Unified View to Greedy Geometric Routing Algorithms in Ad Hoc Netowrks	Christiane Lammersen, Melanie Schmidt and Christian Sohler. Probabilistic k-Median Clustering in Data Streams	Deepak Ajwani and Norbert Zeh. Topological Sorting of Large DAGs with Small Path Cover
15:50 – 16:15		Reinhard Bauer, Moritz Baum, Ignaz Rutter and Dorothea Wagner. On the Complexity of Partitioning Graphs for Arc-Flags	Hongyu Liang, Tiancheng Lou, Haisheng Tan, Amy Yuexuan Wang and Dongxiao Yu. Complexity of Connectivity in Cognitive Radio Networks Through Spectrum Assignment	Guilherme D. da Fonseca, Celina M. H. de Figueiredo, Vinícius G. P. de Sá and Raphael Machado. Linear Time Approximation for Dominating Sets and Independent Dominating Sets in Unit Disk Graphs	Lars Arge, Herman Haverkort and Constantinos Tsirogiannis. Fast Generation of Multiple Resolution Instances of Raster Data Sets
16:15 – 16:40		Samitha Samaranayake, Sebastien Blandin and Alex Bayen. Speedup techniques for the stochastic on-time arrival problem	Yann Disser, Matus Mihalak, Subir Kumar Ghosh and Peter Widmayer. Mapping a polygon with holes using a compass	Reza Dorrigiv, Robert Fraser, Meng He, Shahin Kamali, Akitoshi Kawamura, Alejandro López-Ortiz and Diego Seco. On Minimum- and Maximum-Weight Minimum Spanning Trees with Neighborhoods	Elad Verbin and Wei Yu. Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings
16:40 – 17:10	coffee break
	IPEC – Red Hall Chair: Vangelis Paschos IPEC 5	ATMOS – Iris Hall Chair: Paolo Toth Scheduling and Shunting	ALGOSENSORS – Rose Hall Chair: Sotiris Nikoletseas Optimization and Stability	WAOA – Orchid Hall Chair: Kirk Pruhs Online Algorithms	MASSIVE – Silver Hall Chair: John Iacono MASSIVE 3
17:10 – 17:35	Petteri Kaski, Mikko Koivisto and Jesper Nederlof. Homomorphic Hashing for Sparse Coefficient Extraction	Tim Nonner and Alexander Souza. Optimal Algorithms for Train Shunting and Relaxed List Update Problems	Sivan Albagli-Kim, Leah Epstein, Hadas Shachnai and Tami Tamir. Packing Resizable Items with Application to Video Delivery over Wireless Networks	Akira Matsubayashi. Optimal Online Page Migration on Three Points	Jérémy Barbay, Ankur Gupta, Srinivasa Rao Satti and Jonathan P. Sorenson. Near-Optimal Online Multiselection in Internal and External Memory
17:35 – 18:00	Sepp Hartung, Christian Komusiewicz and André Nichterlein. Parameterized Algorithmics for Finding 2-Clubs: Upper and Lower Bounds and Computational Experiments	Brigitte Jaumard, Thai Hoa Le, Huaining Tian, Ali Akgunduz and Peter Finnie. A Dynamic Row/Column Management Algorithm for Freight Train Scheduling	Pierre Leone and Elad Michael Schiller. Self-Stabilizing TDMA algorithms for Dynamic Wireless Ad-hoc Networks	Lucas Bang, Wolfgang Bein and Lawrence Larmore. R-LINE: A Better Randomized 2-Server Algorithm on the Line	Casper Kejlberg-Rasmussen, Konstantinos Tsakalidis and Kostas Tsichlas. I/O-Efficient Dynamic Planar Range Skyline Queries
17:35 – 18:00			Stefan Hoffmann and Egon Wanke. Metric Dimension for Gabriel Unit Disk Graphs is NP-Complete
18:00 – 18:25	Markus Bläser and Radu Curticapean. Weighted counting of k-matchings is #W[1]-hard	Banafsheh Khosravi, Julia A. Bennell and Chris N. Potts. Train Scheduling and Rescheduling in the UK with a Modified Shifting Bottleneck Procedure	Panel Session	János Balogh, József Békési, György Dósa, Hans Kellerer and Zsolt Tuza. Black and White Bin Packing	Dan Feldman, Melanie Schmidt and Christian Sohler. Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering
18:25 – 18:50		Christopher Bayliss, Geert De Maere, Jason Atkin and Marc Paelinck. Probabilistic Airline Reserve Crew Scheduling	Panel Session	Alejandro López-Ortiz and Alejandro Salinger. Minimizing Cache Usage in Paging
19:00 – 20:00	IPEC – Red Hall business meeting	ATMOS – Iris Hall business meeting	ALGOSENSORS – Rose Hall business meeting		MASSIVE – Silver Hall business meeting

09:00 – 10:00	Plenary – Orchid Hall Subhash Suri: Geometric Computing over Uncertain Data Chair: Amotz Bar-Noy (ALGOSENSORS)
10:00 – 10:30	coffee break
	IPEC – Red Hall Chair: Marek Cygan IPEC 6	WAOA – Orchid Hall Chair: Rob van Stee Scheduling	ALGOSENSORS – Rose Hall Chair: Takeshi Tokuyama Sensor Networks
10:30 – 10:55	Kenta Kitsunai, Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki and Toshihiro Tano. Computing directed pathwidth in O(1.89^n) time	Adam Kurpisz, Monaldo Mastrolilli and Georgios Stamoulis. Online Approximation Schemes for Makespan Scheduling Problems	David Chan and David Kirkpatrick. Approximating Barrier Resilience for Arrangements of Non-Identical Disk Sensors
10:55 – 11:20	James Abello, Pavel Klavík, Jan Kratochvíl and Tomáš Vyskočil. MSOL Restricted Contractibility to Planar Graphs	Anupam Gupta, Ravishankar Krishnaswamy and Kirk Pruhs. Online Primal-Dual For Non-linear Optimization with Applications to Speed Scaling	Rom Aschner, Matthew Katz and Gila Morgenstern. Symmetric Connectivity with Directional Antennas
11:20 – 11:45	Michael Elberfeld, Christoph Stockhusen and Till Tantau. On the Space Complexity of Parameterized Problems	Christoph Dürr, Ioannis Milis, Julien Robert and Georgios Zois. Approximating the Throughput by Coolest First Scheduling	Johannes Wendeberg and Christian Schindelhauer. Polynomial Time Approximation Algorithms for Localization based on Unknown Signals
11:45 – 12:10	Adam Bouland, Anuj Dawar and Eryk Kopczyński. On Tractable Parameterizations of Graph Isomorphism	Janardhan Kulkarni and Kamesh Munagala. Algorithms for Cost Aware Scheduling	Hadassa Daltrophe, Shlomi Dolev and Zvi Lotker. Big Data Interpolation An Efficient Sampling Alternative for Sensor Data Aggregation
12:10 – 13:30	lunch
13:30 – 14:30	Plenary – Orchid Hall Andreas Björklund: The path taken for k-path Chair: Erik Jan van Leeuwen (IPEC)
14:30 – 15:00	coffee break
15:00 – 16:00	Plenary – Orchid Hall Nikhil Bansal: The Primal-Dual approach for Online Algorithms Chair: Thomas Erlebach (WAOA)
	IPEC – Red Hall Chair: Andreas Björklund IPEC 7	WAOA – Orchid Hall Chair: Borut Robič Algorithmic Game Theory	ALGOSENSORS – Rose Hall Chair: Amotz Bar-Noy Open problems session
16:05 – 16:30	Petteri Kaski, Mikko Koivisto and Janne H. Korhonen. Fast Monotone Summation over Disjoint Sets	Vittorio Bilò. A Unifying Tool for Bounding the Quality of Non-Cooperative Solutions in Weighted Congestion Games
16:30 – 16:55	Christian Komusiewicz and Manuel Sorge. Finding Dense Subgraphs of Sparse Graphs	Vittorio Bilò, Michele Flammini, Gianpiero Monaco and Luca Moscardelli. Some Anomalies of Farsighted Strategic Behavior.
16:55 – 17:25	coffee break
	IPEC – Red Hall Chair: Erik Jan van Leeuwe IPEC 8	WAOA – Orchid Hall Chair: Thomas Erlebach Approximation Algorithms
17:25 – 17:50	Naomi Nishimura and Narges Simjour. Enumerating neighbour and closest strings	Martin Niemeier and Andreas Wiese. Scheduling with an Orthogonal Resource Constraint
17:50 – 18:15	Jörg Flum and Moritz Müler. Some definitorial suggestions for parameterized proof complexity	Sara Ahmadian and Chaitanya Swamy. Improved Approximation Guarantees for Lower-Bounded Facility Location
18:15 – 18:40		Therese Biedl. A 4-approximation for the height of 2-connected outer-planar graph drawings
18:40 – 19:05		Trivikram Dokka, Marin Bougeret, Vincent Boudet, Rodolphe Giroudeau and Frits Spieksma. Approximation Algorithms for the Wafer to Wafer Integration Problem