8th Workshop on Approximation and Online Algorithms

9th - 10th September 2010
University of Liverpool, United Kingdom

Accepted Papers

  1. Magnus Bordewich. “On the approximation complexity hierarchy”
  2. Martin R. Ehmsen, Jens S. Kohrt and Kim S. Larsen. “List Factoring and Relative Worst Order Analysis”
  3. János Balogh, József Békési and Gábor Galambos. “New Lower Bounds for Certain Bin Packing Algorithms”
  4. Britta Peis and Andreas Wiese. “Throughput Maximization for Periodic Packet Routing on Trees and Grids”
  5. Rob van Stee. “An improved algorithm for online rectangle filling”
  6. Elliot Anshelevich, Bugra Caskurlu and Ameya Hate. “Strategic Multiway Cut and Multicut Games”
  7. Patrick Briest and Heiko Röglin. “The Power of Uncertainty: Bundle-Pricing for Unit-Demand Customers”
  8. Kirk Pruhs, Julien Robert and Nicolas Schabanel. “Minimizing Maximum Flowtime of Jobs with Arbitrary Parallelizability”
  9. Chandra Chekuri, Avigdor Gal, Sungjin Im, Samir Khuller, Jian Li, Richard McCutchen, Benjamin Moseley and Louiqa Raschid. “New Models and Algorithms for Throughput Maximization in Broadcast Scheduling”
  10. Konstantin Makarychev and Yury Makarychev. “How to Play Unique Games on Expanders”
  11. Caroline Jagtenberg, Uwe Schwiegelshohn and Marc Uetz. “Lower bounds for Smith's rule in stochastic machine scheduling”
  12. Ho-Leung Chan, Tak-Wah Lam and Rongbin Li. “Tradeoff between Energy and Throughput for Online Deadline Scheduling”
  13. Daniel Dressler and Martin Skutella. “An FPTAS for Flows over Time with Aggregate Arc Capacities”
  14. Tomoyuki Yamakami. “Approximate Counting for Complex-Weighted Boolean Constraint Satisfaction Problems”
  15. Danny Z. Chen, Rudolf Fleischer and Jian Li. “Densest k-Subgraph Approximation on Intersection Graphs”
  16. Spyridon Antonakopoulos. “Approximating Directed Buy-at-bulk Network Design”
  17. Aparna Das, Claire Mathieu and Shay Mozes. “The Train Delivery Problem - Vehicle Routing Meets Bin Packing”
  18. Fedor V. Fomin, Petr Golovach and Dimitrios Thilikos. “Approximation algorithms for domination search”
  19. Andreas Karrenbauer and Thomas Rothvoss. “A 3/2-approximation algorithm for rate-monotonic multiprocessor scheduling of implicit-deadline tasks”
  20. David Pritchard. “k-Edge-Connectivity: Approximation and LP Relaxation”
  21. Lior Kamma and Zeev Nutov. “Approximating Survivable Networks with Minimum Number of Steiner Points”
  22. Tak-Wah Lam, Chi-Man Liu and Hing-Fung Ting. “Online Tracking of the Dominance Relationship of Distributed Multi-dimensional Data”
  23. Claire Mathieu and Adrian Vladu. “Online Ranking for Tournament Graphs”