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