| Description |
1 online resource (x, 254 pages) : illustrations |
| Series |
Lecture notes in computer science, 0302-9743 ; 5893 |
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues |
|
Lecture notes in computer science ; 5893
|
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues
|
| Contents |
On the competitiveness of the online asymmetric and Euclidean Steiner tree problems / Spyros Angelopoulos -- Extension of the Nemhauser and Trotter Theorem to generalized vertex cover with applications / Reuven Bar-Yehuda, Danny Hermelin, and Dror Rawitz -- Price fluctuations : to buy or to rent / Marcin Bienkowski -- Approximation algorithms for multiple strip packing / Marin Bougeret, Pierre Francois Dutot, Klaus Jansen, Christina Otte, and Denis Trystram -- Approximating frequent items in asynchronous data stream over a sliding window / Ho-Leung Chan, Tak-Wah Lam, Lap-Kei Lee, and Hing-Fung Ting -- Longest wait first for broadcast scheduling (extended abastract) / Chandra Chekuri, Sungjin Im, and Benjamin Moseley -- The routing open shop problem : new approximation algorithms / Ilya Chernykh, Nikita Dryuck, Alexander Kononov, and Sergey Sevastyanov -- On the price of stability for undirected network design / George Christodoulou, Christine Chung, Katrina Ligett, Evangelia Pyrga, and Rob van Stee -- Finding dense subgraphs in G(n, 1/2) / Atish Das Sarma, Amit Deshpande, and Ravi Kannan -- Parameterized analysis of paging and list update algorithms / Reza Dorrigiv, Martin R. Ehmsen, and Alejandro López-Ortiz -- Online scheduling of bounded length jobs to maximize throughput / Christoph Dürr, Łukasz Jeż, and Kim Thang Nguyen -- On the additive constant of the k-server work function algorithm / Yuval Emek, Pierre Fraigniaud, Amos Korman, and Adi Rosén -- A (4+e)-approximation for the minimum-weight dominating set problem in unit disk graphs / Thomas Erlebach and Matús̆ Mihalák -- Guard games on graphs : keep the intruder out! / Fedor V. Fomin, Petr A. Golovach, and Daniel Lokshtanov -- Between a rock and a hard place : the two-to-one assignment problem / Dries Goossens, Sergey Polyakovskiy, Frits C.R. Spieksma, and Gerhard J. Woeginger -- Scheduling and packing malleable tasks with precedence constraints of bounded width / Elisabeth Günther, Felix G. König, and Nicole Megow -- Online minimization knapsack problem / Xin Han and Kazuhisa Makino -- Optimization problems in multiple subtree graphs / Danny Hermelin and Dror Rawitz -- Multi-criteria TSP : min and max combined / Bodo Manthey -- Packet routing : complexity and algorithms / Britta Peis, Martin Skutella, and Andreas Wiese -- Minimal cost reconfiguration of data placement in storage area network / Hadas Shachnai, Gal Tamir, and Tami Tamir -- Competitive multi-dimensional dynamic bin packing via L-shape bin packing / Prudence W.H. Wong and Fencol C.C. Yung |
| Summary |
Annotation This book constitutes the thoroughly refereed post workshop proceedings of the 7th International Workshop on Approximation and Online Algorithms, WAOA 2009, held in Copenhagen, Denmark, in September 2009 as part of the ALGO 2009 conference event. The 22 revised full papers presented were carefully reviewed and selected from 62 submissions. The workshop covered areas such as algorithmic game theory, approximation classes, coloring and partitioning, competitive analysis, computational finance, cuts and connectivity, geometric problems, inapproximability results, mechanism design, network design, packing and covering, paradigms for design and analysis of approximation and online algorithms, parameterized complexity, randomization techniques, real-world applications, andscheduling problems |
| Bibliography |
Includes bibliographical references and index |
| Notes |
Print version record |
| In |
Springer eBooks |
| Subject |
Online algorithms -- Congresses
|
|
Mathematical optimization -- Congresses
|
|
Algorithms
|
|
Computing Methodologies
|
|
algorithms.
|
|
Informatique.
|
|
Mathematical optimization
|
|
Online algorithms
|
| Genre/Form |
proceedings (reports)
|
|
Conference papers and proceedings
|
|
Conference papers and proceedings.
|
|
Actes de congrès.
|
| Form |
Electronic book
|
| Author |
Bampis, Evripidis
|
|
Jansen, Klaus
|
| ISBN |
9783642124501 |
|
364212450X |
|
