Approximation and Online Algorithms : 9th International Workshop, WAOA 2011, Saarbrücken, Germany, September 8-9, 2011, Revised selected papers / Roberto Solis-Oba, Giuseppe Persiano (eds.).

By: WAOA 2011 (2011 : Saarbrücken, Germany)
Contributor(s): Solis-Oba, Roberto | Persiano, Giuseppe
Material type: TextTextSeries: SerienbezeichnungLecture notes in computer science: 7164.; LNCS sublibrary: Publisher: Berlin ; New York : Springer, ©2012Description: 1 online resource (x, 273 pages)Content type: text Media type: computer Carrier type: online resourceISBN: 9783642291166; 3642291163; 3642291155; 9783642291159Other title: WAOA 2011Subject(s): Online algorithms -- Congresses | Approximation algorithms -- Congresses | Informatique | Approximation algorithms | Online algorithms | Computer science | Computer software | Electronic data processing | Computational complexity | Algorithms | Algorithm Analysis and Problem Complexity | Discrete Mathematics in Computer Science | Numeric Computing | Information Systems Applications (incl. Internet)Genre/Form: Electronic books. | Conference papers and proceedings. | Computer software. Additional physical formats: Printed edition:: No titleDDC classification: 005.1 LOC classification: QA76.9.A43 | W36 2011Online resources: Click here to access online
Contents:
Approximation Algorithms for Scheduling and Packing Problems / Klaus Jansen -- Approximating Subset k-Connectivity Problems / Zeev Nutov -- Learning in Stochastic Machine Scheduling / Sebastián Marbán, Cyriel Rutten and Tjark Vredeveld -- An Online Algorithm Optimally Self-tuning to Congestion for Power Management Problems / Wolfgang Bein, Naoki Hatta, Nelson Hernandez-Cons, Hiro Ito and Shoji Kasahara, et al. -- Single Approximation for Biobjective Max TSP / Cristina Bazgan, Laurent Gourvès, Jérôme Monnot and Fanny Pascual -- Parameterized Approximation Algorithms for Hitting Set / Ljiljana Brankovic and Henning Fernau -- Approximation Algorithms for the Maximum Leaf Spanning Tree Problem on Acyclic Digraphs / Nadine Schwartges, Joachim Spoerhase and Alexander Wolff -- Optimization over Integers with Robustness in Cost and Few Constraints / Kai-Simon Goetzmann, Sebastian Stiller and Claudio Telha -- A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines without Preemption / Tomáš Ebenlendr and Jiří Sgall -- Scheduling Jobs on Identical and Uniform Processors Revisited / Klaus Jansen and Christina Robenek.
Approximation Algorithms for Fragmenting a Graph against a Stochastically-Located Threat / David B. Shmoys and Gwen Spencer -- Non-clairvoyant Weighted Flow Time Scheduling on Different Multi-processor Models / Jianqiao Zhu, Ho-Leung Chan and Tak-Wah Lam -- A New Perspective on List Update: Probabilistic Locality and Working Set / Reza Dorrigiv and Alejandro López-Ortiz -- OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm / Gerth Stølting Brodal, Gabriel Moruz and Andrei Negoescu -- Faster and Simpler Approximation of Stable Matchings / Katarzyna Paluch -- Simpler 3/4-Approximation Algorithms for MAX SAT / Anke van Zuylen -- On Online Algorithms with Advice for the k-Server Problem / Marc P. Renault and Adi Rosén -- Improved Lower Bound for Online Strip Packing / (Extended Abstract) / Rolf Harren and Walter Kern -- Competitive Router Scheduling with Structured Data / Yishay Mansour, Boaz Patt-Shamir and Dror Rawitz -- Approximation with a Fixed Number of Solutions of Some Biobjective Maximization Problems / Cristina Bazgan, Laurent Gourvès and Jérôme Monnot -- Generalized Maximum Flows over Time / Martin Groß and Martin Skutella -- The Price of Anarchy for Minsum Related Machine Scheduling / Ruben Hoeksma and Marc Uetz.
Summary: Annotation This book constitutes the thoroughly refereed post-proceedings of the 9th International Workshop on Approximation and Online Algorithms, WAOA 2011, held in Saarbrücken, Germany, in September 2011. The 21 papers presented were carefully reviewed and selected from 48 submissions. The volume also contains an extended abstract of the invited talk of Prof. Klaus Jansen. The Workshop on Approximation and Online Algorithms focuses on the design and analysis of algorithms for online and computationally hard problems. Both kinds of problems have a large number of applicationsin a wide variety of fields. Topics of interest for WAOA 2011 were: 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 and scheduling 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 author index.

Approximation Algorithms for Scheduling and Packing Problems / Klaus Jansen -- Approximating Subset k-Connectivity Problems / Zeev Nutov -- Learning in Stochastic Machine Scheduling / Sebastián Marbán, Cyriel Rutten and Tjark Vredeveld -- An Online Algorithm Optimally Self-tuning to Congestion for Power Management Problems / Wolfgang Bein, Naoki Hatta, Nelson Hernandez-Cons, Hiro Ito and Shoji Kasahara, et al. -- Single Approximation for Biobjective Max TSP / Cristina Bazgan, Laurent Gourvès, Jérôme Monnot and Fanny Pascual -- Parameterized Approximation Algorithms for Hitting Set / Ljiljana Brankovic and Henning Fernau -- Approximation Algorithms for the Maximum Leaf Spanning Tree Problem on Acyclic Digraphs / Nadine Schwartges, Joachim Spoerhase and Alexander Wolff -- Optimization over Integers with Robustness in Cost and Few Constraints / Kai-Simon Goetzmann, Sebastian Stiller and Claudio Telha -- A Lower Bound on Deterministic Online Algorithms for Scheduling on Related Machines without Preemption / Tomáš Ebenlendr and Jiří Sgall -- Scheduling Jobs on Identical and Uniform Processors Revisited / Klaus Jansen and Christina Robenek.

Approximation Algorithms for Fragmenting a Graph against a Stochastically-Located Threat / David B. Shmoys and Gwen Spencer -- Non-clairvoyant Weighted Flow Time Scheduling on Different Multi-processor Models / Jianqiao Zhu, Ho-Leung Chan and Tak-Wah Lam -- A New Perspective on List Update: Probabilistic Locality and Working Set / Reza Dorrigiv and Alejandro López-Ortiz -- OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm / Gerth Stølting Brodal, Gabriel Moruz and Andrei Negoescu -- Faster and Simpler Approximation of Stable Matchings / Katarzyna Paluch -- Simpler 3/4-Approximation Algorithms for MAX SAT / Anke van Zuylen -- On Online Algorithms with Advice for the k-Server Problem / Marc P. Renault and Adi Rosén -- Improved Lower Bound for Online Strip Packing / (Extended Abstract) / Rolf Harren and Walter Kern -- Competitive Router Scheduling with Structured Data / Yishay Mansour, Boaz Patt-Shamir and Dror Rawitz -- Approximation with a Fixed Number of Solutions of Some Biobjective Maximization Problems / Cristina Bazgan, Laurent Gourvès and Jérôme Monnot -- Generalized Maximum Flows over Time / Martin Groß and Martin Skutella -- The Price of Anarchy for Minsum Related Machine Scheduling / Ruben Hoeksma and Marc Uetz.

Annotation This book constitutes the thoroughly refereed post-proceedings of the 9th International Workshop on Approximation and Online Algorithms, WAOA 2011, held in Saarbrücken, Germany, in September 2011. The 21 papers presented were carefully reviewed and selected from 48 submissions. The volume also contains an extended abstract of the invited talk of Prof. Klaus Jansen. The Workshop on Approximation and Online Algorithms focuses on the design and analysis of algorithms for online and computationally hard problems. Both kinds of problems have a large number of applicationsin a wide variety of fields. Topics of interest for WAOA 2011 were: 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 and scheduling problems.

There are no comments for this item.

to post a comment.

Powered by Koha