+612 9045 4394
Approximation and Online Algorithms : First International Workshop, Waoa 2003, Budapest, Hungary, September 16-18, 2003, Revised Papers - Klaus Jansen

Approximation and Online Algorithms

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

By: Klaus Jansen (Editor), Roberto Solis-Oba (Editor)

Paperback Published: 12th February 2004
ISBN: 9783540210795
Number Of Pages: 268

Share This Book:


or 4 easy payments of $31.26 with Learn more
Ships in 5 to 9 business days

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

Online coloring of intervals with bandwidthp. 1
Open block scheduling in optical communication networksp. 13
Randomized priority algorithmsp. 27
Tradeoffs in worst-case equilibriap. 41
Load balancing of temporary tasks in the l[subscript p] normp. 53
Simple on-line algorithms for call control in cellular networksp. 67
Fractional and integral coloring of locally-symmetric sets of paths on binary treesp. 81
A 5/4-approximation algorithm for scheduling identical malleable tasksp. 95
Optimal on-line algorithms to minimize makespan on two machines with resource augmentationp. 109
Scheduling AND/OR-networks on identical parallel machinesp. 123
Combinatorial interpretations of duel fitting and primal fittingp. 137
On the approximability of the minimum fundamental cycle basis problemp. 151
The pledge algorithm reconsidered under errors in sensors and motionp. 165
The online matching problem on a linep. 179
How to whack molesp. 192
Online deadline scheduling : team adversary and restartp. 206
Minimum sum multicoloring on the edges of treesp. 214
Scheduling to minimize average completion time revisited : deterministic on-line algorithmsp. 227
On-line extensible bin packing with unequal bin sizesp. 235
Energy consumption in radio networks : selfish agents and rewarding mechanismsp. 248
Power consumption problems in ad-hoc wireless networksp. 252
A combinatorial approximation algorithm for the multicommodity flow problemp. 256
Disk graphs : a short surveyp. 260
Combinatorial techniques for memory power state scheduling in energy-constrained systemsp. 265
Author indexp. 269
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9783540210795
ISBN-10: 3540210792
Series: Lecture Notes in Computer Science,
Audience: General
Format: Paperback
Language: English
Number Of Pages: 268
Published: 12th February 2004
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 1.52
Weight (kg): 0.4