Approximation and online algorithms : 7th international workshop, WAOA 2009, Copenhagen, Denmark, September 10-11, 2009 : revised papers / Evripidis Bampis, Klaus Jansen (eds.).

By: WAOA 2009 (2009 : Copenhagen, Denmark)
Contributor(s): Bampis, Evripidis | Jansen, Klaus
Material type: TextTextSeries: SerienbezeichnungLecture notes in computer science: 5893.; LNCS sublibrary: Publisher: Berlin : Springer, ©2010Description: 1 online resource (x, 254 pages) : illustrationsContent type: text Media type: computer Carrier type: online resourceISBN: 9783642124501; 364212450XOther title: WAOA 2009Subject(s): Online algorithms -- Congresses | Mathematical optimization -- Congresses | Algorithms | Computing Methodologies | Algorithmes en ligne -- Congrès | Optimisation mathématique -- Congrès | Informatique | Mathematical optimization | Online algorithmsGenre/Form: Congress. | Electronic books. | Conference papers and proceedings. Additional physical formats: Print version:: Approximation and online algorithms.DDC classification: 005.1 LOC classification: QA76.9.A43 | W42 2009Online resources: Click here to access online
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.
Tags from this library: No tags from this library for this title. Log in to add tags.
    Average rating: 0.0 (0 votes)
Item type Current location Collection Call number Status Date due Barcode Item holds
eBook eBook e-Library

Electronic Book@IST

EBook Available
Total holds: 0

Includes bibliographical references and index.

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.

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.

Print version record.

There are no comments for this item.

to post a comment.

Powered by Koha