Algorithmic Aspects in Information and Management

1. Front Matter

   PDF

2. Double Partition: (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs

   • Ding-Zhu Du

   Pages 1-1

3. Nash Bargaining Via Flexible Budget Markets

   • Vijay V. Vazirani

   Pages 2-2

4. On the Minimum Hitting Set of Bundles Problem

   • Eric Angel, Evripidis Bampis, Laurent Gourvès

   Pages 3-14

5. Speed Scaling with a Solar Cell

   • Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs

   Pages 15-26

6. Engineering Label-Constrained Shortest-Path Algorithms

   • Chris Barrett, Keith Bisset, Martin Holzer, Goran Konjevod, Madhav Marathe, Dorothea Wagner

   Pages 27-37

7. New Upper Bounds on Continuous Tree Edge-Partition Problem

   • Robert Benkoczi, Binay Bhattacharya, Qiaosheng Shi

   Pages 38-49

8. A Meeting Scheduling Problem Respecting Time and Space

   • Florian Berger, Rolf Klein, Doron Nussbaum, Jörg-Rüdiger Sack, Jiehua Yi

   Pages 50-59

9. Fixed-Parameter Algorithms for Kemeny Scores

   • Nadja Betzler, Michael R. Fellows, Jiong Guo, Rolf Niedermeier, Frances A. Rosamond

   Pages 60-71

10. The Distributed Wireless Gathering Problem

    • Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela, Leen Stougie

    Pages 72-83

11. Approximating Maximum Edge 2-Coloring in Simple Graphs Via Local Improvement

    • Zhi-Zhong Chen, Ruka Tanahashi

    Pages 84-96

12. An Improved Randomized Approximation Algorithm for Maximum Triangle Packing

    • Zhi-Zhong Chen, Ruka Tanahashi, Lusheng Wang

    Pages 97-108

13. Line Facility Location in Weighted Regions

    • Yam Ki Cheung, Ovidiu Daescu

    Pages 109-119

14. Algorithms for Temperature-Aware Task Scheduling in Microprocessor Systems

    • Marek Chrobak, Christoph Dürr, Mathilde Hurand, Julien Robert

    Pages 120-130

15. Engineering Comparators for Graph Clusterings

    • Daniel Delling, Marco Gaertler, Robert Görke, Dorothea Wagner

    Pages 131-142

16. On the Fast Searching Problem

    • Danny Dyer, Boting Yang, Öznur Yaşar

    Pages 143-154

17. Confidently Cutting a Cake into Approximately Fair Pieces

    • Jeff Edmonds, Kirk Pruhs, Jaisingh Solanki

    Pages 155-164

18. Copeland Voting Fully Resists Constructive Control

    • Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe

    Pages 165-176

19. The Complexity of Power-Index Comparison

    • Piotr Faliszewski, Lane A. Hemaspaandra

    Pages 177-187

20. Facility Location Problems: A Parameterized View

    • Michael Fellows, Henning Fernau

    Pages 188-199

This book constitutes the refereed proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management, AAIM 2008, held in Shanghai, China, in June 2008. The 30 revised full papers presented together with abstracts of 2 invited talks were carefully reviewed and selected from 53 submissions. The papers cover original algorithmic research on immediate applications and/or fundamental problems pertinent to information management and management science. Topics addressed are: approximation algorithms, geometric data management, biological data management, graph algorithms, computational finance, mechanism design, computational game theory, network optimization, data structures, operations research, discrete optimization, online algorithms, FPT algorithms, and scheduling algorithms.

• algorithm
• algorithms
• data structure
• data structures
• game theory
• management
• optimization
• algorithm analysis and problem complexity

Policies and ethics