Algorithms and Complexity

1. Front Matter

   PDF

2. Approximation Algorithms for Disjoint st-Paths with Minimum Activation Cost

   • Hasna Mohsen Alqahtani, Thomas Erlebach

   Pages 1-12

3. Parameterized Complexity and Kernel Bounds for Hard Planning Problems

   • Christer Bäckström, Peter Jonsson, Sebastian Ordyniak, Stefan Szeider

   Pages 13-24

4. Selfish Resource Allocation in Optical Networks

   • Evangelos Bampas, Aris Pagourtzis, George Pierrakos, Vasilis Syrgkanis

   Pages 25-36

5. Average Optimal String Matching in Packed Strings

   • Djamal Belazzougui, Mathieu Raffinot

   Pages 37-48

6. Parameterized Complexity of DAG Partitioning

   • René van Bevern, Robert Bredereck, Morgan Chopin, Sepp Hartung, Falk Hüffner, André Nichterlein et al.

   Pages 49-60

7. Four Measures of Nonlinearity

   • Joan Boyar, Magnus Find, René Peralta

   Pages 61-72

8. On the Characterization of Plane Bus Graphs

   • Till Bruckdorfer, Stefan Felsner, Michael Kaufmann

   Pages 73-84

9. Online Multi-dimensional Dynamic Bin Packing of Unit-Fraction Items

   • Mihai Burcea, Prudence W. H. Wong, Fencol C. C. Yung

   Pages 85-96

10. A Greedy Approximation Algorithm for Minimum-Gap Scheduling

    • Marek Chrobak, Uriel Feige, Mohammad Taghi Hajiaghayi, Sanjeev Khanna, Fei Li, Seffi Naor

    Pages 97-109

11. Exponential Complexity of Satisfiability Testing for Linear-Size Boolean Formulas

    • Evgeny Dantsin, Alexander Wolpert

    Pages 110-121

12. Linear Time Distributed Swap Edge Algorithms

    • Ajoy K. Datta, Lawrence L. Larmore, Linda Pagli, Giuseppe Prencipe

    Pages 122-133

13. Decentralized Throughput Scheduling

    • Jasper de Jong, Marc Uetz, Andreas Wombacher

    Pages 134-145

14. New Results on Stabbing Segments with a Polygon

    • José Miguel Díaz-Báñez, Matias Korman, Pablo Pérez-Lantero, Alexander Pilz, Carlos Seara, Rodrigo I. Silveira

    Pages 146-157

15. Improving the H _k -Bound on the Price of Stability in Undirected Shapley Network Design Games

    • Yann Disser, Andreas Emil Feldmann, Max Klimm, Matúš Mihalák

    Pages 158-169

16. Complexity of Barrier Coverage with Relocatable Sensors in the Plane

    • Stefan Dobrev, Stephane Durocher, Mohsen Eftekhari, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc et al.

    Pages 170-182

17. Succinct Permanent Is NEXP-Hard with Many Hard Instances

    • Shlomi Dolev, Nova Fandina, Dan Gutfreund

    Pages 183-196

18. Money-Based Coordination of Network Packets

    • Pavlos S. Efraimidis, Remous-Aris Koutsiamanis

    Pages 197-208

19. Truthful Many-to-Many Assignment with Private Weights

    • Bruno Escoffier, Jérôme Monnot, Fanny Pascual, Olivier Spanjaard

    Pages 209-220

20. Competitive Online Clique Clustering

    • Aleksander Fabijan, Bengt J. Nilsson, Mia Persson

    Pages 221-233

This book constitutes the refereed conference proceedings of the 8th International Conference on Algorithms and Complexity, CIAC 2013, held in Barcelona, Spain, during May 22-24, 2013. The 31 revised full papers presented were carefully reviewed and selected from 75 submissions. The papers present current research in all aspects of computational complexity and the use, design, analysis and experimentation of efficient algorithms and data structures.

• algorithmic game theory
• decision tree complexity
• plane graphs
• read-once formulae
• string matching
• algorithm analysis and problem complexity
• data structures

• School of Engineering, Department of Computer Engineering and Informatics, University of Patras, Patras, Greece

  Paul G. Spirakis

• LSI Department, Edif Omega, Universitat Politècnica de Catalunya, Barcelona, Spain

  Maria Serna

Policies and ethics