Theory and Applications of Models of Computation

1. Front Matter

   PDF

2. Online Scheduling on a CPU-GPU Cluster

   • Lin Chen, Deshi Ye, Guochuan Zhang

   Pages 1-9

3. Throughput Maximization for Speed-Scaling with Agreeable Deadlines

   • Eric Angel, Evripidis Bampis, Vincent Chau, Dimitrios Letsios

   Pages 10-19

4. Temperature Aware Online Algorithms for Minimizing Flow Time

   • Martin Birks, Stanley Fung

   Pages 20-31

5. Priority Queues and Sorting for Read-Only Data

   • Tetsuo Asano, Amr Elmasry, Jyrki Katajainen

   Pages 32-41

6. (1 + ε)-Distance Oracles for Vertex-Labeled Planar Graphs

   • Mingfei Li, Chu Chung Christopher Ma, Li Ning

   Pages 42-51

7. Group Nearest Neighbor Queries in the L ₁ Plane

   • Hee-Kap Ahn, Sang Won Bae, Wanbin Son

   Pages 52-61

8. Modelling the Power Supply Network – Hardness and Approximation

   • Alexandru Popa

   Pages 62-71

9. Approximation Algorithms for a Combined Facility Location Buy-at-Bulk Network Design Problem

   • Andreas Bley, S. Mehdi Hashemi, Mohsen Rezapour

   Pages 72-83

10. k-means++ under Approximation Stability

    • Manu Agarwal, Ragesh Jaiswal, Arindam Pal

    Pages 84-95

11. An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure

    • Mingyu Xiao, Hiroshi Nagamochi

    Pages 96-107

12. Non-crossing Connectors in the Plane

    • Jan Kratochvíl, Torsten Ueckerdt

    Pages 108-120

13. Minimax Regret 1-Sink Location Problems in Dynamic Path Networks

    • Siu-Wing Cheng, Yuya Higashikawa, Naoki Katoh, Guanqun Ni, Bing Su, Yinfeng Xu

    Pages 121-132

14. A Notion of a Computational Step for Partial Combinatory Algebras

    • Nathanael L. Ackerman, Cameron E. Freer

    Pages 133-143

15. Selection by Recursively Enumerable Sets

    • Wolfgang Merkle, Frank Stephan, Jason Teutsch, Wei Wang, Yue Yang

    Pages 144-155

16. On the Boundedness Property of Semilinear Sets

    • Oscar H. Ibarra, Shinnosuke Seki

    Pages 156-168

17. Turing Machines Can Be Efficiently Simulated by the General Purpose Analog Computer

    • Olivier Bournez, Daniel S. Graça, Amaury Pouly

    Pages 169-180

18. Computing with and without Arbitrary Large Numbers

    • Michael Brand

    Pages 181-192

19. On the Sublinear Processor Gap for Parallel Architectures

    • Alejandro López-Ortiz, Alejandro Salinger

    Pages 193-204

20. On Efficient Constructions of Short Lists Containing Mostly Ramsey Graphs

    • Marius Zimand

    Pages 205-211

This book constitutes the refereed proceedings of the 10th International Conference on Theory and Applications of Models of Computation, TAMC 2013, held in Hong Kong, China, in May 2013. The 31 revised full papers presented were carefully reviewed and selected from 70 submissions. Bringing together a wide range of researchers with interests in computational theory and applications, the papers address the three main themes of the conference which were computability, complexity, and algorithms and present current research in these fields with aspects to theoretical computer science, algorithmic mathematics, and applications to the physical sciences.

• complexity
• elliptic curve
• provable security
• public-key cryptography
• steganography
• algorithm analysis and problem complexity

• The University of Hong Kong, Hong Kong

  T-H. Hubert Chan

• The Chinese University of Hong Kong, Hong Kong

  Lap Chi Lau

• Department of Computer Science, Stanford University, Stanford, USA

  Luca Trevisan

Policies and ethics