Approximation and Online Algorithms

1. Front Matter

   PDF

2. Pricing Commodities, or How to Sell When Buyers Have Restricted Valuations

   • Robert Krauthgamer, Aranyak Mehta, Atri Rudra

   Pages 1-14

3. Improved Lower Bounds for Non-utilitarian Truthfulness

   • Iftah Gamzu

   Pages 15-26

4. Buyer-Supplier Games: Optimization over the Core

   • Nedialko B. Dimitrov, C. Greg Plaxton

   Pages 27-40

5. Very Large-Scale Neighborhoods with Performance Guarantees for Minimizing Makespan on Parallel Machines

   • Tobias Brueggemann, Johann L. Hurink, Tjark Vredeveld, Gerhard J. Woeginger

   Pages 41-54

6. A 3/2-Approximation for the Proportionate Two-Machine Flow Shop Scheduling with Minimum Delays

   • Alexander A. Ageev

   Pages 55-66

7. Online Algorithm for Parallel Job Scheduling and Strip Packing

   • Johann L. Hurink, Jacob Jan Paulus

   Pages 67-74

8. Geometric Spanners with Small Chromatic Number

   • Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Michiel Smid, Norbert Zeh

   Pages 75-88

9. Approximating Largest Convex Hulls for Imprecise Points

   • Maarten Löffler, Marc van Kreveld

   Pages 89-102

10. A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem

    • Alexander A. Ageev, Artem V. Pyatkin

    Pages 103-115

11. Covering the Edges of Bipartite Graphs Using K _2,2 Graphs

    • Dorit S. Hochbaum, Asaf Levin

    Pages 116-127

12. On Min-Max r-Gatherings

    • Amitai Armon

    Pages 128-141

13. On the Max Coloring Problem

    • Leah Epstein, Asaf Levin

    Pages 142-155

14. Full and Local Information in Distributed Decision Making

    • Panagiota N. Panagopoulou, Paul G. Spirakis

    Pages 156-169

15. The Minimum Substring Cover Problem

    • Danny Hermelin, Dror Rawitz, Romeo Rizzi, Stéphane Vialette

    Pages 170-183

16. A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs

    • José R. Correa, Cristina G. Fernandes, Martín Matamala, Yoshiko Wakabayashi

    Pages 184-192

17. On the Online Unit Clustering Problem

    • Leah Epstein, Rob van Stee

    Pages 193-206

18. Better Bounds for Incremental Medians

    • Marek Chrobak, Mathilde Hurand

    Pages 207-217

19. Minimum Weighted Sum Bin Packing

    • Leah Epstein, Asaf Levin

    Pages 218-231

20. Approximation Schemes for Packing Splittable Items with Cardinality Constraints

    • Leah Epstein, Rob van Stee

    Pages 232-245

The Fifth Workshop on Approximation and Online Algorithms (WAOA 2007) focused on the design and analysis of algorithms for online and computationally hard problems. Both kinds of problems have a large number of applications from a variety of ?elds. WAOA 2007 took place in Eilat, Israel, during October 11–12, 2007. The workshop was part of the ALGO 2007 event that also hosted ESA 2007, and PEGG 2007. The previous WAOA workshops were held in Budapest (2003), Rome (2004), Palma de Mallorca (2005) and Zurich (2006). The proceedings of these previous WAOA workshops have appeared as LNCS volumes 2909, 3351, 3879 and 4368, respectively. Topics of interest for WAOA 2007 were: algorithmic game theory, appro- mation classes, coloring and partitioning, competitive analysis, computational ?nance, cuts and connectivity, geometric problems, inapproximability results, mechanism design, network design, packing and covering, paradigms for design and analysis of approximation and online algorithms, randomization techniques, real-world applications, and scheduling problems. In response to the call for - pers, we received 56 submissions. Each submission was reviewed by at least three referees, and the vast majority by at least four referees. The submissions were mainly judged on originality, technical quality, and relevance to the topics of the conference. Based on the reviews, the Program Committee selected 22 papers. We are grateful to Andrei Voronkov for providing the EasyChair conference system which was used to manage the electronic submissions, the review process, and the electronic PC meeting. It made our task much easier.

• Performance
• algorithm
• algorithm analysis
• algorithm design
• algorithmics
• algorithms
• approximation algorithms
• combinatorial optimization
• competitive analysis
• complexity
• computational graph theory
• decision making
• design
• game theory
• optimization
• algorithm analysis and problem complexity
• data structures

Policies and ethics