Algorithms -- ESA 2011

1. Front Matter

   PDF

2. Approximation Algorithms I

   1. Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility under Budget Constraints

      • Akiyoshi Shioura

      Pages 1-12

   2. Approximating the Smallest 2-Vertex Connected Spanning Subgraph of a Directed Graph

      • Loukas Georgiadis

      Pages 13-24

   3. Improved Approximation Algorithms for Bipartite Correlation Clustering

      • Nir Ailon, Noa Avigdor-Elgrabli, Edo Liberty, Anke van Zuylen

      Pages 25-36

   4. Bounds on Greedy Algorithms for MAX SAT

      • Matthias Poloczek

      Pages 37-48

3. Computational Geometry I

   1. Approximating Minimum Manhattan Networks in Higher Dimensions

      • Aparna Das, Emden R. Gansner, Michael Kaufmann, Stephen Kobourov, Joachim Spoerhase, Alexander Wolff

      Pages 49-60

   2. On Isolating Points Using Disks

      • Matt Gibson, Gaurav Kanade, Kasturi Varadarajan

      Pages 61-69

   3. An Output-Sensitive Approach for the L ₁/L _∞ k-Nearest-Neighbor Voronoi Diagram

      • Chih-Hung Liu, Evanthia Papadopoulou, D. T. Lee

      Pages 70-81

   4. Can Nearest Neighbor Searching Be Simple and Always Fast?

      • Victor Alvarez, David G. Kirkpatrick, Raimund Seidel

      Pages 82-92

4. Game Theory

   1. On the Approximation Performance of Fictitious Play in Finite Games

      • Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen, Carmine Ventre

      Pages 93-105

   2. How Profitable Are Strategic Behaviors in a Market?

      • Ning Chen, Xiaotie Deng, Jie Zhang

      Pages 106-118

   3. Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms

      • George Christodoulou, Kurt Mehlhorn, Evangelia Pyrga

      Pages 119-130

5. Graph Algorithms I

   1. Algorithms for Finding a Maximum Non-k-linked Graph

      • Yusuke Kobayashi, Yuichi Yoshida

      Pages 131-142

   2. An \(\mathcal{O}(n^4)\) Time Algorithm to Compute the Bisection Width of Solid Grid Graphs

      • Andreas Emil Feldmann, Peter Widmayer

      Pages 143-154

   3. Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time

      • Jakub Łącki, Piotr Sankowski

      Pages 155-166

6. Stable Matchings and Auctions

   1. Near-Popular Matchings in the Roommates Problem

      • Chien-Chung Huang, Telikepalli Kavitha

      Pages 167-179

   2. The Hospitals/Residents Problem with Quota Lower Bounds

      • Koki Hamada, Kazuo Iwama, Shuichi Miyazaki

      Pages 180-191

   3. Multi-parameter Mechanism Design under Budget and Matroid Constraints

      • Monika Henzinger, Angelina Vidali

      Pages 192-202

7. Optimization

   1. Quantified Linear Programs: A Computational Study

      • Thorsten Ederer, Ulf Lorenz, Alexander Martin, Jan Wolf

      Pages 203-214

   2. Recoverable Robustness by Column Generation

      • P. C. Bouman, J. M. van den Akker, J. A. Hoogeveen

      Pages 215-226

This book constitutes the refereed proceedings of the 19th Annual European Symposium on Algorithms, ESA 2011, held in Saarbrücken, Germany, in September 2011 in the context of the combined conference ALGO 2011. The 67 revised full papers presented were carefully reviewed and selected from 255 initial submissions: 55 out of 209 in track design and analysis and 12 out of 46 in track engineering and applications. The papers are organized in topical sections on approximation algorithms, computational geometry, game theory, graph algorithms, stable matchings and auctions, optimization, online algorithms, exponential-time algorithms, parameterized algorithms, scheduling, data structures, graphs and games, distributed computing and networking, strings and sorting, as well as local search and set systems.

• combinatorial optimization
• linear programming
• online algorithms
• parameterized algorithms
• worst case analysis
• algorithm analysis and problem complexity
• data structures

• Dipartimento di Informatica e Sistemistica, University of Rome " La Sapienza", Roma, Italy

  Camil Demetrescu

• School of Computer Science, Reykjavik University, Reykjavik, Iceland

  Magnús M. Halldórsson

Policies and ethics