Tapas Program

download pdf version

Monday, 18/4 2011

9:00 am to 9:25 am Registration
9:25 am to 9:30 am Opening Remarks: Alberto Marchetti-Spaccamela and Michael Segal, Program Co-Chairs
9:30 am to 10:30 am Invited talk: Managing Power Heterogeneity by Kirk Pruhs
10:30 am to 11:00 am Coffee Break
11:00 am to 12:15 am Session 1: Scheduling
  • Energy-efficient due date scheduling by Ho-Leung Chan, Tak-Wah Lam and Rongbin Li
  • MIP Formulations for Flowshop Scheduling with Limited Buffers by Janick Frasch, Sven Oliver Krumke and Stephan Westphal
  • Algorithms for Scheduling with Power Control in Wireless Networks by Tigran Tonoyan
12:30 am to 2:00 pm Lunch Break
2:00 pm to 3:15 pm Session 2: Algorithms in Graphs
  • Exact Algorithms for Intervalizing Colored Graphs by Hans L. Bodlaender and Johan M. M. van Rooij
  • A Comparison of Three Algorithms for Approximating the Distance Distribution in Real-World Graphs by Pierluigi Crescenzi, Roberto Grossi, Leonardo Lanzi and Andrea Marino
  • Exploiting Bounded Signal Flow for Graph Orientation Based on Cause–Effect Pairs by Britta Dorn, Falk Hüffner, Dominikus Krüger, Rolf Niedermeier and Johannes Uhlmann
3:15 pm to 3:45 pm Coffee Break
3:45 pm to 5:25 pm Session 4: Optimization
  • A Scenario-Based Approach for Robust Linear Optimization by Marc Goerigk and Anita Schöbel
  • Robust Line Planning in case of Multiple Pools and Disruptions by Apostolos Bessas, Spyros Kontogiannis and Christos Zaroliagis
  • New Bounds for Old Algorithms: On the Average-Case Behavior of Classic Single-Source Shortest Path Approaches by Andrei Negoescu, Ulrich Meyer and Volker Weichert
  • Alternative Route Graphs in Road Networks by Roland Bader, Jonathan Dees, Robert Geisberger and Peter Sanders
5:30 pm to 7:00 pm Welcome Reception

Tuesday 19/4, 2011

9:00 am to 10:00 am Invited Talk: Distributed Decision Problems: The Locality Angle by Shay Kutten
10:00 am to 10:30 am Coffee Break
10:30 am to 12:10 am Session 3: Potpourri
  • On Greedy and Submodular Matrices by Ulrich Faigle, Walter Kern and Britta Peis
  • Go with the Flow: The Direction-Based Frechet Distance of Polygonal Curves by Atlas F. Cook IV and Mark de Berg
  • Improved Taxation Rate for Bin Packing Games by Walter Kern and Xian Qiu Conflict Propagation and Component Recursion for Canonical Labeling by Tommi Junttila and Petteri Kaski
12:15 am to 2:00 pm Lunch Break
2:00 pm to 3:15 pm Session 4: Scheduling 2
  • Speed Scaling for Energy and Performance with Instantaneous Parallelism by Hongyang Sun, Yuxiong He and Wen-Jing Hsu
  • Speed Scaling to Manage Temperature by Leon Atkins, Guillaume Aupy, Daniel Cole and Kirk Pruhs
  • An Approximative Criterion for the Potential of Energetic Reasoning by Jens Schulz, Timo Berthold and Stefan Heinz
  • Multi-channel assignment for communication in radio networks by Dariusz Kowalski and Mariusz Rokicki
8:00 pm Banquet

Wednesday 20/4, 2011

9:00 am to 10:00 am Invited talk: The Mathematics of Mobility by Paolo Santi
10:00 am to 10:30 am Coffee Break
10:30 am to 12:10 am Session 6: Algorithms in Graphs 3
  • L(2,1)-Labeling of Unigraphs by Tiziana Calamoneri and Rossella Petreschi
  • Improved approximation algorithms for the Max-Edge Coloring problem by Giorgio Lucarelli and Ioannis Milis
  • 3-Hitting Set on bounded degree hypergraphs: Upper and lower bounds on the kernel size by Iyad Kanj and Fenghui Zhang
  • Computing strongly connected components in the streaming model by Luigi Laura and Federico Santaroni
12:15 pm Lunch