A PDF version of the program can be found here.
| 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) | ||
| 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:25-18:45 | |||
| 18:45-19:15 | WABI Business Meeting | ||
| 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) | |||
| 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 |
|
|
| 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 |
|
| 14:50-15:15 |
|
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 |
||
| 15:45-16:10 |
|
Coping with Interferences:From
Maximum Coverage to Planning Cellular Networks
David Amzallag, Seffi Naor, and Danny Raz |
| 16:10-16:35 |
|
Competitive Online
Multicommodity Routing
Tobias Harks, Stefan Heinz, and Marc E. Pfetsch |
| 16:35-17:00 |
|
Online Distributed Object Migration
David Scot Taylor |
| 17:00-17:10 | Short Break | |
| 17:10-17:35 |
|
Approximation Algorithms for
Scheduling Problems with Exact Delays
Alexander A. Ageev and Alexander V. Kononov |
| 17:35-18:00 |
|
Reversal Distance for Strings with
Duplicates: Linear Time Approximation using Hitting Set
Petr Kolman and Tomasz Walen |
