Conference Program

A PDF version of the program can be found here.

Monday, September 11th

08:50-09:00 Opening Remarks (Room ML D28)
09:00-09:50 Plenary Talk (Room ML D28)
László Lovász: Sampling, integration and volume computation by Markov chains
09:50-10:00 Short Break
ESA 1 (Room CAB G11)
Chair: Yossi Azar
ESA 2 (Room CAB G61)
Chair: Friedhelm Meyer auf der Heide
WABI 1 (Room CAB G51)
10:00-10:25 A Unified Approach to Approximating Partial Covering Problems
Jochen Könemann, Ojas Parekh, and Danny Segev
Navigating Low-Dimensional and Hierarchical Population Networks
Ravi Kumar, David Liben-Nowell, and Andrew Tomkins
Measures of Codon Bias in Yeast, the tRNA Pairing Index, and Possible DNA Repair Mechanisms
Markus Friberg, Pedro Gonnet, Yves Barral, Nicol Schraudolph, and Gaston Gonnet
10:25-10:50 Approximate k-Steiner Forests via the Lagrangian Relaxation Technique with Internal Preprocessing
Danny Segev and Gil Segev
A doubling dimension threshold theta(loglog n) for augmented graphs navigability
Pierre Fraigniaud, Emmanuelle Lebhar, and Zvi Lotker
Decomposing Metabolomic Isotope Patterns
Sebastian Böcker, Matthias Letzel, Zsuzsanna Lipták, and Anton Pervukhin
10:50-11:15 Coffee Break
ESA 3 (Room CAB G11)
Chair: Dimitris Fotakis
ESA 4 (Room CAB G61)
Chair: Gerth S. Brodal
WABI 2 (Room CAB G51)
11:15-11:40 Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games
Bruno Codenotti, Mauro Leoncini, and Giovanni Resta
Less Hashing, Same Performance: Building a Better Bloom Filter
Adam Kirsch and Michael Mitzenmacher
A Method to Design Standard HMMs with Desired Length Distribution for Biological Sequence Analysis
Hongmei Zhu, Jiaxin Wang, Zehong Yang, and Yixu Song
11:40-12:05 Cheating by Men in the Gale-Shapley Stable Matching Algorithm
Chien-Chung Huang
Negative Examples for Sequential Importance Sampling of Binary Contingency Tables
Ivona Bezakova, Alistair Sinclair, Daniel Štefankovic, and Eric Vigoda
Efficient Model-Based Clustering for LC-MS Data
Marta Luksza, Boguslaw Kluge, Jerzy Ostrowski, Jakub Karczmarski, and Anna Gambin
12:05-12:30 Taxes for linear atomic congestion games
Ioannis Caragiannis, Christos Kaklamanis, and Panagiotis Kanellopoulos
Stochastic Shortest Paths via Quasi-Convex Maximization
Evdokia Nikolova, Michael Mitzenmacher, Jonathan A. Kelner, and Matthew Brand
A Bayesian Algorithm for Reconstructing Bacterial Signaling Networks
Lukas Burger and Erik van Nimwegen
12:30-14:00 Lunch Break
ESA 5 (Room CAB G11)
Chair: Leah Epstein
ESA 6 (Room CAB G61)
Chair: Thomas Erlebach
WABI 3 (Room CAB G51)
14:00-14:25 Approximation results for preemptive stochastic online scheduling
Nicole Megow and Tjark Vredeveld
The Engineering of a Compression Boosting Library: Theory vs Practice in BWT compression
Paolo Ferragina, Raffaele Giancarlo, and Giovanni Manzini
Linear-Time Haplotype Inference on Pedigree without Recombinations
Mee Yee Chan, Wun-Tat Chan, Francis Chin, Stanley Fung and Ming-Yang Kao
14:25-14:50 Preemptive Online Scheduling: Optimal Algorithms for All Speeds
Tomáš Ebenlendr, Wojciech Jawor, and Jirí Sgall
An Improved Construction for Counting Bloom Filters
Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, and George Varghese
Phylogenetic Network Inferences through Efficient Haplotyping
Yinglei Song, Chunmei Liu, Russell Malmberg, and Liming Cai
14:50-15:15 Lower and Upper Bounds on FIFO Buffer Management in QoS Switches
Matthias Englert and Matthias Westermann
Engineering Highway Hierarchies
Peter Sanders and Dominik Schultes
Beaches of Islands of Tractability: Algorithms for Parsimony and Minimum Perfect Phylogeny Haplotyping Problems
Leo van Iersel, Judith Keijsper, Steven Kelk, and Leen Stougie
15:15-15:40 Competitive Analysis of Flash-Memory Algorithms
Avraham Ben-Aroya and Sivan Toledo
Does Path Cleaning Help in Dynamic All-Pairs Shortest Paths?
Camil Demetrescu, Pompeo Faruolo, Giuseppe F. Italiano, and Mikkel Thorup
On the Complexity of SNP Block Partitioning Under the Perfect Phylogeny Model
Jens Gramm, Tzvika Hartman, Till Nierhoff, Roded Sharan, and Till Tantau
15:40-16:10 Coffee Break
ESA 7 (Room CAB G11)
Chair: Rob van Stee
ESA 8 (Room CAB G61)
Chair: Dan Halperin
WABI 4 (Room CAB G51)
16:10-16:35 Resource Allocation in Bounded Degree Trees
Reuven Bar-Yehuda, Michael Beder, Yuval Cohen, and Dror Rawitz
Algorithmic Aspects of Proportional Symbol Maps
Sergio Cabello, Herman Haverkort, Marc van Kreveld, and Bettina Speckmann
How Many Transcripts does it Take to Reconstruct the Splice Graph?
Paul Jenkins, Rune Lyngsø, and Jotun Hein
16:35-17:00 Graph coloring with rejection
Leah Epstein, Asaf Levin, and Gerhard Woeginger
Kinetic Algorithms via Self-Adjusting Computation
Umut Acar, Guy Blelloch, Kanat Tangwongsan, and Jorge Vittes
Multiple Structure Alignment and Consensus Identification for Proteins
Jieping Ye, Ivaylo Ilinkin, Ravi Janardan, and Adam Isom
17:00-17:25 Single machine precedence constrained scheduling is a vertex cover problem
Christoph Ambühl and Monaldo Mastrolilli
Out-of-Order Event Processing in Kinetic Data Structures
Mohammad Ali Abam, Pankaj Agarwal, Mark de Berg, and Hai Yu
Procrastination Leads to Efficient Filtration for Local Multiple Alignment
Aaron Darling, Todd Treangen, Louxin Zhang, Carla Kuiken, Xavier Messeguer, and Nicole Perna
17:25-17:50 Finding total unimodularity in optimization problems solved by linear programs
Christoph Dürr and Mathilde Hurand
Reporting Flock Patterns
Marc Benkert, Joachim Gudmundsson, Florian Hübner, and Thomas Wolle
Controlling Size when Aligning Multiple Genomic Sequences with Duplications
Minmei Hou, Piotr Berman, Louxin Zhang, and Webb Miller
18:00-20:00 Reception (CABinett)

Tuesday, September 12th

09:00-09:50 Plenary Talk (Room ML D28)
Kurt Mehlhorn: Reliable and Efficient Geometric Computing
09:50-10:00 Short Break
ESA 9 (Room CAB G11)
Chair: Susanne Albers
ESA 10 (Room CAB G61)
Chair: Rolf Niedermeier
WABI 5 (Room CAB G51)
10:00-10:25 Greedy in Approximation Algorithms
Julian Mestre
Multiline Addressing by Network Flow
Friedrich Eisenbrand, Andreas Karrenbauer, Martin Skutella, and Chihao Xu
Reducing Distortion in Phylogenetic Networks
Daniel Huson, Mike Steel, and Jim Whitfield
10:25-10:50 Popular Matchings in the Capacitated House Allocation Problem
David Manlove and Colin Sng
On exact algorithms for treewidth
Hans Bodlaender, Fedor Fomin, Arie Koster, Dieter Kratsch, and Dimitrios Thilikos
Imputing Supertrees and Supernetworks from Quartets
Barbara Holland, Glenn Conner, Katharina Huber, and Vincent Moulton
10:50-11:15 Coffee Break
ESA 11 (Room CAB G11)
Chair: Andrew Goldberg
ESA 12 (Room CAB G61)
Chair: Ulrich Meyer
WABI 6 (Room CAB G51)
11:15-11:40 Approximating almost all instances of Max-Cut within a ratio above the Hastad threshold
Alexis Kaporis, Lefteris Kirousis, and Elias Stavropoulos
The Price of Resiliency: A Case Study on Sorting with Memory Faults
Umberto Ferraro Petrillo, Irene Finocchi, and Giuseppe Italiano
A Unifying View of Genome Rearrangements
Anne Bergeron, Julia Mixtacki, and Jens Stoye
11:40-12:05 Balancing Applied to Maximum Network Flow Problems
Robert Tarjan, Julie Ward, Bin Zhang, Yunhong Zhou, and Jia Mao
How Branch Mispredictions Affect Quicksort
Kanela Kaligosi and Peter Sanders
Efficient Sampling of Transpositions and Inverted Transpositions for Bayesian MCMC
István Miklós, Timothy Brooks Paige, and Péter Ligeti
12:05-12:30 Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data
Brian Dean, Michel Goemans, and Nicole Immorlica
Skewed Binary Search Trees
Gerth Brodal and Gabriel Moruz
Alignment with Nonoverlapping Inversions in Cubic Time
Augusto Vellozo, Carlos Eduardo Alves, and Alair do Lago
12:30-14:00 Lunch Break
14:00-14:50 Plenary Talk (Room ML D28)
Lisa Fleischer: Finding Equilibria through Natural Play: Tatonnement and the Market Problem
14:50-15:00 Short Break
ESA 13 (Room CAB G11)
Chair: Lars Arge
ESA 14 (Room CAB G61)
Chair: Bettina Speckmann
WABI 7 (Room CAB G51)
15:00-15:25 Violator Spaces: Structure and Algorithms
Bernd Gärtner, Jirí Matoušek, Leo Rüst, and Petr Skovron
On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization
Khaled Elbassioni
Accelerating Motif Discovery: Motif Matching on Parallel Hardware
Geir Kjetil Sandve, Magnar Nedland, Oyvind Bo Syrstad, Lars Andreas Eidsheim, Osman Abul, and Finn Drablos
15:25-15:50 Path Hitting in Acyclic Graphs
Ojas Parekh and Danny Segev
An LP-Designed Algorithm for Constraint Satisfaction
Alexander Scott and Gregory Sorkin
Segmenting Motifs in Protein-Protein Interface Surfaces
Jeff M. Phillips, Johannes Rudolph, and Pankaj K. Agarwal
15:50-16:20 Coffee Break
ESA 15 (Room CAB G11)
Chair: Hans Bodlaender
ESA 16 (Room CAB G61)
Chair: Mariette Yvinec
WABI 8 (Room CAB G51)
16:20-16:45 Dynamic Programming and Fast Matrix Multiplication
Frederic Dorn
Kinetic Collision Detection for Convex Fat Objects
Mohammad Ali Abam, Mark de Berg, Sheung-Hung Poon, and Bettina Speckmann
Protein Sidechain Placement through MAP Estimation and Problem-Size Reduction
Eun-Jong Hong and Tomás Lozano-Pérez
16:45-17:10 An O(n^3 (loglog n/log n)^{5/4}) Time Algorithm for All Pairs Shortest Path
Yijie Han
Traversing the Machining Graph
Danny Chen, Rudolf Fleischer, Jian Li, and Haitao Wang
On the Complexity of the Crossing Contact Map Pattern Matching Problem
Shuai Cheng Li and Ming Li
17:10-17:35 I/O-Efficient Undirected Shortest Paths with Unbounded Weights
Ulrich Meyer and Norbert Zeh
Frechet Distance for Curves, Revisited
Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, and Carola Wenk
A Fuzzy Dynamic Programming Approach to Predict RNA Secondary Structure
Dandan Song and Zhidong Deng
17:35-18:00 Cooperative TSP
Amitai Armon, Adi Avidor, and Oded Schwartz
Dynamic Connectivity for Axis-Parallel Rectangles
Peyman Afshani and Timothy Chan
Landscape Analysis for Protein Folding Simulation in the H-P Model
Kathleen Steinhöfel, Alexandros Skaliotis, and Andreas A. Albrecht
18:00-18:25 ESA Business Meeting Rapid ab initio RNA Folding Including Pseudoknots via Graph Tree Decomposition
Jizhen Zhao, Russell Malmberg, and Liming Cai
18:45-19:15 WABI Business Meeting

Wednesday, September 13th

09:00-09:50 Plenary Talk (Room ML D28)
Ron Shamir: Some Computational Challenges in Today's Bio-Medicine
09:50-10:00 Short Break
ESA 17 (Room CAB G11)
Chair: Norbert Zeh
ESA 18 (Room CAB G61)
Chair: Christos Zaroliagis
WABI 9 (Room CAB G51) IWPEC 1 (Room CAB G59)
Chair: Dieter Kratsch
10:00-10:25 Latency Constrained Aggregation in Sensor Networks
Luca Becchetti, Peter Korteweg, Alberto Marchetti-Spaccamela, Martin Skutella, Leen Stougie, and Andrea Vitaletti
Spanners with Slack
T-H. Hubert Chan, Michael Dinitz, and Anupam Gupta
Flux-Based vs. Topology-Based Similarity of Metabolic Genes
Oleg Rokhlenko, Tomer Shlomi, Roded Sharan, Eytan Ruppin, and Ron Pinter
Applying modular decomposition to parameterized bicluster editing
Fábio Protti, Maise Dantas da Silva, and Jayme Luiz Szwarcfiter
10:25-10:50 Contention Resolution with Heterogeneous Job Sizes
Michael Bender, Jeremy Fineman, and Seth Gilbert
Dynamic Algorithms for Maintaining Graph Spanners
Surender Baswana
Combinatorial Methods for Disease Association Search and Susceptibility Prediction
Dumitru Brinza and Alexander Zelikovsky
The Cluster Editing Problem: Implementations and Experiments
Frank Dehne, Michael Langston, Xuemei Luo, Sylvain Pitre, Peter Shaw, and Yun Zhang
10:50-11:15 Coffee Break
ESA 19 (Room CAB G11)
Chair: Lisa Fleischer
ESA 20 (Room CAB G61)
Chair: Stefan Szeider
WABI 10 (Room CAB G51) IWPEC 2 (Room CAB G59)
Chair: Fedor Fomin
11:15-11:40 Subspace Sampling and Relative-Error Matrix Approximation: Column-Row-Based Methods
Petros Drineas, Michael Mahoney, and S. Muthukrishnan
Univariate polynomial real root isolation: Continued Fractions revisited
Iaonnis Emiris and Elias Tsigaridas
Integer Linear Programs for Discovering Approximate Gene Clusters
Sven Rahmann and Gunnar Klau
The Parameterized Complexity of Maximality and Minimality Problems
Yijia Chen and Jörg Flum
11:40-12:05 Spectral Clustering by Recursive Partitioning
Anirban Dasgupta, John Hopcroft, Ravi Kannan, and Pradipta Mitra
Exact and Efficient Construction of Planar Minkowski Sums using the Convolution Method
Ron Wein
Approximation Algorithms for Bi-clustering Problems
Lusheng Wang, Yu Lin, and Xiaowen Liu
Parameterizing MAXSNP problems above Guaranteed Values
Meena Mahajan, Venkatesh Raman, and Somnath Sikdar
12:05-12:30 Region-Restricted Clustering for Geographic Data Mining
Joachim Gudmundsson, Marc van Kreveld, and Giri Narasimham
Robust, Generic and Efficient Construction of Envelopes of Surfaces in Three-Dimensional Space
Michal Meyerovitch
Improving the Layout of Oligonucleotide Microarrays: Pivot Partitioning
Sven Rahmann and Sérgio A. de Carvalho Jr.
Randomized approximations of parameterized counting problems
Moritz Müller
12:30-14:00 Lunch Break
14:00-14:50 Plenary Talk (Room ML D28)
Erik Demaine: Origami, Linkages, and Polyhedra: Folding with Algorithms
14:50-15:00 Short Break
ESA 21 (Room CAB G11)
Chair: Mark de Berg
ESA 22 (Room CAB G61)
Chair: Lene M. Favrholdt
WABI 11 (Room CAB G51) IWPEC 3 (Room CAB G59)
Chair: Dániel Marx
15:00-15:25 Necklaces, Convolutions, and X+Y
David Bremner, Timothy Chan, Erik Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Ileana Streinu, and Perouz Taslakian
Parallel machine scheduling through column generation: minimax objective functions
Marjan van den Akker, Han Hoogeveen, and Jules van Kempen
Accelerating the Computation of Elementary Modes Using Pattern Trees
Marco Terzer and Jörg Stelling
Fixed-Parameter Complexity of Minimum Profile Problems
Gregory Gutin, Stefan Szeider, and Anders Yeo
15:25-15:50 Inner-Product Based Wavelet Synopses for Range-Sum Queries
Yossi Matias and Daniel Urieli
An MINLP solution method for a water network problem
Cristiana Bragalli, Claudia D'Ambrosio, Jon Lee, Andrea Lodi, and Paolo Toth
A Linear-Time Algorithm for Studying Genetic Variation
Nikola Stojanovic and Piotr Berman
On the OBDD Size for Graphs of Bounded Tree- and Clique-Width
Klaus Meer and Dieter Rautenbach
15:50-16:20 Coffee Break
ESA 23 (Room CAB G11)
Chair: Subhash Suri
ESA 24 (Room CAB G61)
Chair: Jan Kratochvíl
WABI 12 (Room CAB G51) IWPEC 4 (Room CAB G59)
Chair: Jörg Flum
16:20-16:45 Purely Functional Worst Case Constant Time Catenable Sorted Lists
Gerth Brodal, Christos Makris, and Kostas Tsichlas
Deciding Relaxed Two-Colorability - A Hardness Jump
Robert Berke and Tibor Szabó
New Constructive Heuristics for DNA Sequencing by Hybridization
Christian Blum and Mateu Yábar Vallès
Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
Liming Cai and Xiuzhen Huang
16:45-17:10 Compressed Indexes for Approximate String Matching
Ho-Leung Chan, Tak-Wah Lam, Wing-Kin Sung, Siu-Lung Tam, and Swee-Seong Wong
Minimum Transversals in Posi-modular Systems
Mariko Sakashita, Kazuhisa Makino, Hiroshi Nagamochi, and Satoru Fujishige
Optimal Probing Patterns for Sequencing By Hybridization
Dekel Tsur
On Parameterized Approximability
Yijia Chen, Martin Grohe, and Magdalena Grüber
17:10-17:35 Near-Entropy Hotlink Assignments
Karim Douïeb and Stefan Langerman
Distributed almost exact approximations for minor-closed families
Andrzej Czygrinow and Michal Hanckowiak
Gapped Permutation Patterns for Comparative Genomics
Laxmi Parida
Parameterized Approximation Algorithms
Rodney Downey, Michael Fellows, and Catherine McCartin
17:35-18:00 Estimating Entropy over Data Streams
Lakshminath Bhuvanagiri and Sumit Ganguly
Enumerating Spanning and Connected Subsets in Graphs and Matroids
Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino
Segmentation with an Isochore Distribution
Miklós Csurös, Ming-Te Cheng, Andreas Grimm, Amine Halawani, and Perrine Landreau

18:15-20:00 Reception (Dozentenfoyer)

Thursday, September 14th

09:00-09:50 Plenary Talk (Room ML D28)
Ralf Borndörfer: Directions in Railway and Public Transport Optimization
09:50-10:00 Short Break
IWPEC 5 (Room CAB G11)
Chair: Frank Dehne
WAOA 1 (Room CAB G61)
Chair: Rudolf Fleischer
ATMOS 1 (Room CAB G51)
10:00-10:25 An Exact Algorithm for the Minimum Dominating Clique Problem
Dieter Kratsch and Mathieu Liedloff
Online k-server routing problems
Vincenzo Bonifaci and Leen Stougie
Tutorial: Next Generation Decision Support Systems in Railroad Scheduling
Ravi Ahuja
10:25-10:50 Edge Dominating Set: efficient enumeration-based exact algorithms
Henning Fernau
Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem
Joan Boyar, Martin R. Ehmsen and Kim S. Larsen
10:50-11:15 Coffee Break
IWPEC 6 (Room CAB G11)
Chair: Erik D. Demaine
WAOA 2 (Room CAB G61)
Chair: Kim S. Larsen
ATMOS 2 (Room CAB G51)
11:15-11:40 Parameterized Complexity of Independence and Domination on Geometric Graphs
Dániel Marx
On bin packing with conflicts
Leah Epstein and Asaf Levin
A Column Generation Approach for the Rail Crew Re-Scheduling Problem
Dennis Huisman
11:40-12:05 Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs
Jan Kára and Jan Kratochvíl
Bin packing with rejection revisited
Leah Epstein
An An Efficient MIP Model for Locomotive Scheduling with Time Windows
Martin Aronsson, Per Kreuger, and Jonata Gjerdrum
12:05-12:30 On the parameterized complexity of d-dimensional point set pattern matching
Sergio Cabello, Panos Giannopoulos, and Christian Knauer
Improved online hypercube packing
Xin Han, Deshi Ye, and Yong Zhou
Locomotive and Wagon Scheduling in Freight Transport
Armin Fügenschuh, Henning Homfeld, Andreas Huck, and Alexander Martin
12:30-14:00 Lunch Break
IWPEC 7 (Room CAB G11)
Chair: Jan Arne Telle
WAOA 3 (Room CAB G61)
Chair: Martin Fürer
ATMOS 3 (Room CAB G51)
14:00-14:25 Finding a Minimum Feedback Vertex Set in time O(1.7548^n)
Fedor Fomin, Serge Gaspers, and Artem Pyatkin
Approximating Maximum Cut with Limited Unbalance
Giulia Galbiati and Francesco Maffioli
Periodic Metro Scheduling
Evangelos Bampas, Georgia Kaouri, Michael Lampis, and Aris Pagourtzis
14:25-14:50 The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
Kevin Burrage, Vladimir Estivill-Castro, Michael Fellows, Michael Langston, Shev Mac, and Frances Rosamond
Network Design with Edge-Connectivity and Degree Constraints
Takuro Fukunaga and Hiroshi Nagamochi
A Game-Theoretic Approach to Line Planning
Anita Schöbel and Silvia Schwarze
14:50-15:15 Fixed-parameter tractability results for Full-Degree Spanning Tree and its dual
Jiong Guo, Rolf Niedermeier, and Sebastian Wernicke
Improved Approximation Bounds for Edge Dominating Set in Dense Graphs
Jean Cardinal, Stefan Langerman, and Eythan Levy
QoS-aware Multicommodity Flows and Transportation Planning
George Tsaggouris and Christos Zaroliagis
15:15-15:45 Coffee Break
IWPEC 8 (Room CAB G11)
Chair: Michael A. Langston
WAOA 4 (Room CAB G61)
Chair: Rob van Stee
ATMOS 4 (Room CAB G51)
15:45-16:10 Invited talk
Frank Dehne:
FPT At Work: Using fixed parameter tractability to solve larger instances of hard problems
Bidding to the Top: VCG and Equilibria of Position-Based Auctions
Gagan Aggarwal, Jon Feldman, and S. Muthukrishnan
Robustness and Recovery in Train Scheduling - a Case Study from DSB S-tog a/s
Mads Hofman, Line Madsen, Julie Jespersen Groth, Jens Clausen, and Jesper Larsen
16:10-16:35 The survival of the weakest in networks
Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul Spirakis
Freight Service Design for the Italian Railways Company
Marco Campetella, Guglielmo Lulli, Ugo Pietropaoli, and Nicoletta Ricciardi
16:35-16:45 Greedy Localization, Color-Coding, and Dynamic programming: Improved Algorithms for Matching and Packing Problems
Yang Liu, Songjian Lu, Jianer Chen, and Sing-Hoi Sze
An Experimental Study of the Misdirection Algorithm for Combinatorial Auctions
Piotr Krysta and Jörg Knoche
Short Break
16:45-17:00 ATMOS Business Meeting
17:00-17:10 IWPEC Business Meeting Short Break
17:10-17:35 Approximation Algorithms for Multi-Criteria Traveling Salesman Problems
Bodo Manthey and L. Shankar Ram

17:35-18:00 Worst Case Analysis of Max-Regret and Other Heuristics for Multidimensional Assignment and Traveling Salesman Problems
Gregory Gutin, Boris Goldengorin, and Jing Huang

Friday, September 15th

09:00-09:50 Plenary Talk (Room ML D28)
Uwe Schöning: Moderately exponential algorithms
09:50-10:00 Short Break
IWPEC 9 (Room CAB G11)
Chair: Catherine McCartin
WAOA 5 (Room CAB G61)
Chair: Asaf Levin
10:00-10:25 On the Effective Enumerability of NP Problems
Jianer Chen, Iyad Kanj, Jie Meng, Ge Xia, and Fenghui Zhang
A Randomized Algorithm for Online Unit Clustering
Timothy Chan and Hamid Zarrabi-Zadeh
10:25-10:50 The Parameterized Complexity of Enumerating Frequent Itemsets
Matthew Hamilton, Rhonda Chaytor, and Todd Wareham
On hierarchical diameter-clustering, and the supplier problems
Aparna Das and Claire Kenyon
10:50-11:15 Coffee Break
IWPEC 10 (Room CAB G11)
Chair: Michael Fellows
WAOA 6 (Room CAB G61)
Chair: Marc van Kreveld
11:15-11:40 Random Separation: A New Methodology for Solving Fixed-Cardinality Optimization Problems
Leizhen Cai, Siu Man Chan, and Sio On Chan
Covering Many of Few Points with Unit Disks
Mark de Berg, Sergio Cabello, and Sariel Har-Peled
11:40-12:05 Towards a Taxonomy of Techniques for Designing Parameterized Algorithms
Christian Sloper and Jan Arne Telle
On the minimum corridor connection problem and other generalized geometric problems
Hans Bodlaender, Corinne Feremans, Alexander Grigoriev, Eelko Penninkx, Rene Sitters, and Thomas Wolle
12:05-12:30 Kernels: Annotated, Proper and Induced
Faisal Abu-Khzam and Henning Fernau
Approximate Distance Queries in Disk Graphs
Martin Fürer and Shiva Kasiviswanathan
12:30-14:00 Lunch Break
IWPEC 11 (Room CAB G11)
Chair: Hans Bodlaender
WAOA 7 (Room CAB G61)
Chair: Gregory Gutin
14:00-14:25 Invited Talk
Michael Fellows:
The Lost Continent of Polynomial Time Preprocessing and Kernelization
Approximating the unweighted k-set cover problem: greedy meets local search
Asaf Levin
14:25-14:50 The k-allocation problem and its variants
Dorit S. Hochbaum and Asaf Levin
Online Dynamic Programming Speedups
Amotz Bar-Noy, Mordecai Golin, and Yan Zhang
15:15-15:45 Coffee Break
WAOA 8 (Room CAB G61)
Chair: Thomas Erlebach
Coping with Interferences:From Maximum Coverage to Planning Cellular Networks
David Amzallag, Seffi Naor, and Danny Raz
Competitive Online Multicommodity Routing
Tobias Harks, Stefan Heinz, and Marc E. Pfetsch
Online Distributed Object Migration
David Scot Taylor
17:00-17:10 Short Break
Approximation Algorithms for Scheduling Problems with Exact Delays
Alexander A. Ageev and Alexander V. Kononov
Reversal Distance for Strings with Duplicates: Linear Time Approximation using Hitting Set
Petr Kolman and Tomasz Walen