Skip to main content
SpringerLink
Log in

Approximation and Online Algorithms

First International Workshop, WAOA 2003, Budapest, Hungary, September 16-18, 2003, Revised Papers

  • Conference proceedings
  • © 2004

Overview

Editors:
  1. Roberto Solis-Oba

    1. Department of Computer Science, The University of Western Ontario, London, Canada

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Klaus Jansen

    1. Institute for Computer Science, University of Kiel, Kiel, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

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

Included in the following conference series:

Conference proceedings info: WAOA 2003.

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

Access this book

Log in via an institution
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

Licence this eBook for your library

Institutional subscriptions

Table of contents (24 papers)

  1. Front Matter

    Download chapter PDF

  2. Contributed Talks

    1. Online Coloring of Intervals with Bandwidth

      • Udo Adamy, Thomas Erlebach
      Pages 1-12

    2. Open Block Scheduling in Optical Communication Networks

      • Alexander A. Ageev, Aleksei V. Fishkin, Alexander V. Kononov, Sergey V. Sevastianov
      Pages 13-26

    3. Randomized Priority Algorithms

      • Spyros Angelopoulos
      Pages 27-40

    4. Tradeoffs in Worst-Case Equilibria

      • Baruch Awerbuch, Yossi Azar, Yossi Richter, Dekel Tsur
      Pages 41-52

    5. Load Balancing of Temporary Tasks in the ℓ p Norm

      • Yossi Azar, Amir Epstein, Leah Epstein
      Pages 53-66

    6. Simple On-Line Algorithms for Call Control in Cellular Networks

      • Ioannis Caragiannis, Christos Kaklamanis, Evi Papaioannou
      Pages 67-80

    7. Fractional and Integral Coloring of Locally-Symmetric Sets of Paths on Binary Trees

      • Ioannis Caragiannis, Christos Kaklamanis, Pino Persiano, Anastasios Sidiropoulos
      Pages 81-94

    8. A \(\frac{5}{4}\)-Approximation Algorithm for Scheduling Identical Malleable Tasks

      • Thomas Decker, Thomas Lücking, Burkhard Monien
      Pages 95-108

    9. Optimal On-Line Algorithms to Minimize Makespan on Two Machines with Resource Augmentation

      • Leah Epstein, Arik Ganot
      Pages 109-122

    10. Scheduling AND/OR-Networks on Identical Parallel Machines

      • Thomas Erlebach, Vanessa Kääb, Rolf H. Möhring
      Pages 123-136

    11. Combinatorial Interpretations of Dual Fitting and Primal Fitting

      • Ari Freund, Dror Rawitz
      Pages 137-150

    12. On the Approximability of the Minimum Fundamental Cycle Basis Problem

      • Giulia Galbiati, Edoardo Amaldi
      Pages 151-164

    13. The Pledge Algorithm Reconsidered under Errors in Sensors and Motion

      • Tom Kamphans, Elmar Langetepe
      Pages 165-178

    14. The Online Matching Problem on a Line

      • Elias Koutsoupias, Akash Nanavati
      Pages 179-191

    15. How to Whack Moles

      • Sven O. Krumke, Nicole Megow, Tjark Vredeveld
      Pages 192-205

    16. Online Deadline Scheduling: Team Adversary and Restart

      • Jae-Ha Lee
      Pages 206-213

    17. Minimum Sum Multicoloring on the Edges of Trees

      • Dániel Marx
      Pages 214-226

    18. Scheduling to Minimize Average Completion Time Revisited: Deterministic On-Line Algorithms

      • Nicole Megow, Andreas S. Schulz
      Pages 227-234

    19. On-Line Extensible Bin Packing with Unequal Bin Sizes

      • Deshi Ye, Guochuan Zhang
      Pages 235-247
Back to top

Other volumes

  1. Approximation and Online Algorithms

Keywords

About this book

The Workshop on Approximation and Online Algorithms (WAOA 2003) focused on the design and analysis of algorithms for online and computationally hard problems. Both kinds of problems have a large number of applications ar- ing from a variety of ?elds. The workshop also covered experimental research on approximation and online algorithms. WAOA 2003 took place in Budapest, Hungary, from September 16 to September 18. The workshop was part of the ALGO 2003 event, which also hosted ESA 2003, WABI 2003, and ATMOS 2003. TopicsofinterestforWAOA2003were:competitiveanalysis,inapproximab- ityresults,randomizationtechniques,approximationclasses,scheduling,coloring and partitioning, cuts and connectivity, packing and covering, geometric pr- lems, network design, and applications to game theory and ?nancial problems. In response to our call for papers we received 41 submissions. Each submission was reviewed by at least 3 referees, who judged the papers on originality, quality, and consistency with the topics of the conference. Based on these reviews the program committee selected 19 papers for presentation at the workshop and for publication in this proceedings. This volume contains the 19 selected papers and 5 invited abstracts from an ARACNE minisymposium which took place as part of WAOA.

Editors and Affiliations

  • Department of Computer Science, The University of Western Ontario, London, Canada

    Roberto Solis-Oba

  • Institute for Computer Science, University of Kiel, Kiel, Germany

    Klaus Jansen

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation