Computing and Combinatorics

1. Front Matter

   PDF

2. Keynote

   1. Recent Results for Online Makespan Minimization

      • Susanne Albers

      Pages 1-3

   2. Optimal Stopping Meets Combinatorial Optimization

      • Robert Kleinberg

      Pages 4-4

3. Game Theory

   1. New Bounds for the Balloon Popping Problem

      • Davide Bilò, Vittorio Bilò

      Pages 5-16

   2. On the Sequential Price of Anarchy of Isolation Games

      • Anna Angelucci, Vittorio Bilò, Michele Flammini, Luca Moscardelli

      Pages 17-28

   3. Social Exchange Networks with Distant Bargaining

      • Konstantinos Georgiou, George Karakostas, Jochen Könemann, Zuzanna Stamirowska

      Pages 29-40

   4. The 1/4-Core of the Uniform Bin Packing Game Is Nonempty

      • Walter Kern, Xian Qiu

      Pages 41-52

4. Randomized Algorithms

   1. On the Advice Complexity of the Online L(2,1)-Coloring Problem on Paths and Cycles

      • Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovič, Sacha Krug, Björn Steffen

      Pages 53-64

   2. On Randomized Fictitious Play for Approximating Saddle Points over Convex Sets

      • Khaled Elbassioni, Kazuhisa Makino, Kurt Mehlhorn, Fahimeh Ramezani

      Pages 65-76

   3. A Fast Algorithm for Data Collection along a Fixed Track

      • Otfried Cheong, Radwa El Shawi, Joachim Gudmundsson

      Pages 77-88

   4. Random Methods for Parameterized Problems

      • Qilong Feng, Jianxin Wang, Shaohua Li, Jianer Chen

      Pages 89-100

5. Scheduling Algorithms

   1. DVS Scheduling in a Line or a Star Network of Processors

      • Zongxu Mu, Minming Li

      Pages 101-113

   2. Online Algorithms for Batch Machines Scheduling with Delivery Times

      • Peihai Liu, Xiwen Lu

      Pages 114-121

   3. How to Schedule the Marketing of Products with Negative Externalities

      • Zhigang Cao, Xujin Chen, Changjun Wang

      Pages 122-133

   4. From Preemptive to Non-preemptive Speed-Scaling Scheduling

      • Evripidis Bampis, Alexander Kononov, Dimitrios Letsios, Giorgio Lucarelli, Ioannis Nemparis

      Pages 134-146

6. Computational Theory

   1. Selection from Read-Only Memory with Limited Workspace

      • Amr Elmasry, Daniel Dahl Juhl, Jyrki Katajainen, Srinivasa Rao Satti

      Pages 147-157

   2. Deternimization of Büchi Automata as Partitioned Automata

      • Cong Tian, Zhenhua Duan, Mengfei Yang

      Pages 158-168

   3. On Linear-Size Pseudorandom Generators and Hardcore Functions

      • Joshua Baron, Yuval Ishai, Rafail Ostrovsky

      Pages 169-181

   4. A Fast Algorithm Finding the Shortest Reset Words

      • Andrzej Kisielewicz, Jakub Kowalski, Marek Szykuła

      Pages 182-196

7. Computational Geometry

   1. The Discrete Voronoi Game in a Simple Polygon

      • Aritra Banik, Sandip Das, Anil Maheshwari, Michiel Smid

      Pages 197-207

This book constitutes the refereed proceedings of the 19th International Conference on Computing and Combinatorics, COCOON 2013, held in Hangzhou, China, in June 2013. The 56 revised full papers presented were carefully reviewed and selected from 120 submissions. There was a co-organized workshop on discrete algorithms of which 8 short papers were accepted and a workshop on computational social networks where 12 papers out of 25 submissions were accepted.

• approximation data mining
• graph algorithms
• graph algorithms
• pseudorandom generators
• social network analysis
• algorithm analysis and problem complexity

• Department of Computer Science, University of Texas at Dallas, Richardson, USA

  Ding-Zhu Du

• College of Computer Science and Technology, Zhejiang University, Hangzhou, China

  Guochuan Zhang

Policies and ethics