Skip to main content
  • Conference proceedings
  • © 2007

Approximation and Online Algorithms

4th International Workshop, WAOA 2006, Zurich, Switzerland, September 14-15, 2006, Revised Papers

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 4368)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Conference series link(s): WAOA: International Workshop on Approximation and Online Algorithms

Conference proceedings info: WAOA 2006.

Buy it now

Buying options

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

This is a preview of subscription content, log in via an institution to check for access.

Table of contents (26 papers)

  1. Front Matter

  2. Approximation Algorithms for Scheduling Problems with Exact Delays

    • Alexander A. Ageev, Alexander V. Kononov
    Pages 1-14
  3. Bidding to the Top: VCG and Equilibria of Position-Based Auctions

    • Gagan Aggarwal, Jon Feldman, S. Muthukrishnan
    Pages 15-28
  4. Coping with Interference: From Maximum Coverage to Planning Cellular Networks

    • David Amzallag, Joseph (Seffi) Naor, Danny Raz
    Pages 29-42
  5. Online Dynamic Programming Speedups

    • Amotz Bar-Noy, Mordecai J. Golin, Yan Zhang
    Pages 43-54
  6. Covering Many or Few Points with Unit Disks

    • Mark de Berg, Sergio Cabello, Sariel Har-Peled
    Pages 55-68
  7. On the Minimum Corridor Connection Problem and Other Generalized Geometric Problems

    • Hans Bodlaender, Corinne Feremans, Alexander Grigoriev, Eelko Penninkx, René Sitters, Thomas Wolle
    Pages 69-82
  8. Online k-Server Routing Problems

    • Vincenzo Bonifaci, Leen Stougie
    Pages 83-94
  9. Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem

    • Joan Boyar, Martin R. Ehmsen, Kim S. Larsen
    Pages 95-107
  10. Improved Approximation Bounds for Edge Dominating Set in Dense Graphs

    • Jean Cardinal, Stefan Langerman, Eythan Levy
    Pages 108-120
  11. A Randomized Algorithm for Online Unit Clustering

    • Timothy M. Chan, Hamid Zarrabi-Zadeh
    Pages 121-131
  12. On Hierarchical Diameter-Clustering, and the Supplier Problem

    • Aparna Das, Claire Kenyon
    Pages 132-145
  13. Bin Packing with Rejection Revisited

    • Leah Epstein
    Pages 146-159
  14. On Bin Packing with Conflicts

    • Leah Epstein, Asaf Levin
    Pages 160-173
  15. Approximate Distance Queries in Disk Graphs

    • Martin Fürer, Shiva Prasad Kasiviswanathan
    Pages 174-187
  16. Network Design with Edge-Connectivity and Degree Constraints

    • Takuro Fukunaga, Hiroshi Nagamochi
    Pages 188-201
  17. Approximating Maximum Cut with Limited Unbalance

    • Giulia Galbiati, Francesco Maffioli
    Pages 202-213
  18. Improved Online Hypercube Packing

    • Xin Han, Deshi Ye, Yong Zhou
    Pages 226-239
  19. Competitive Online Multicommodity Routing

    • Tobias Harks, Stefan Heinz, Marc E. Pfetsch
    Pages 240-252

Other Volumes

  1. Approximation and Online Algorithms

Editors and Affiliations

  • Department of Computer Science, University of Leicester, Leicester, UK

    Thomas Erlebach

  • Research Academic Computer Technology Institute &, Department of Computer Engineering and Informatics, University of Patras, Rio, Greece

    Christos Kaklamanis

Bibliographic Information

Buy it now

Buying options

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access