Algorithmic Aspects in Information and Management

by Fleischer, Rudolf; Xu, Jinhui

• ISBN13: 9783540688655
• ISBN10: 354068865X
• Format: Paperback
• Copyright: 2008-08-03
• Publisher: Springer-Verlag New York Inc

Summary

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.

Table of Contents

Double Partition: (6 + [epsilon])-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs	p. 1
Nash Bargaining Via Flexible Budget Markets	p. 2
On the Minimum Hitting Set of Bundles Problem	p. 3
Speed Scaling with a Solar Cell	p. 15
Engineering Label-Constrained Shortest-Path Algorithms	p. 27
New Upper Bounds on Continuous Tree Edge-Partition Problem	p. 38
A Meeting Scheduling Problem Respecting Time and Space	p. 50
Fixed-Parameter Algorithms for Kemeny Scores	p. 60
The Distributed Wireless Gathering Problem	p. 72
Approximating Maximum Edge 2-Coloring in Simple Graphs Via Local Improvement	p. 84
An Improved Randomized Approximation Algorithm for Maximum Triangle Packing	p. 97
Line Facility Location in Weighted Regions	p. 109
Algorithms for Temperature-Aware Task Scheduling in Microprocessor Systems	p. 120
Engineering Comparators for Graph Clusterings	p. 131
On the Fast Searching Problem	p. 143
Confidently Cutting a Cake into Approximately Fair Pieces	p. 155
Copeland Voting Fully Resists Constructive Control	p. 165
The Complexity of Power-Index Comparison	p. 177
Facility Location Problems: A Parameterized View	p. 188
Shortest Path Queries in Polygonal Domains	p. 200
A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem	p. 212
Minimum Cost Homomorphism Dichotomy for Oriented Cycles	p. 224
Minimum Leaf Out-Branching Problems	p. 235
Graphs and Path Equilibria	p. 247
No l Grid-Points in Spaces of Small Dimension	p. 259
The Secret Santa Problem	p. 271
Finding Optimal Refueling Policies in Transportation Networks	p. 280
Scale Free Interval Graphs	p. 292
On Representation of Planar Graphs by Segments	p. 304
An Optimal On-Line Algorithm for Preemptive Scheduling on Two Uniform Machines in the [actual symbol not reproducible][subscript p] Norm	p. 316
An Optimal Strategy for Online Non-uniform Length Order Scheduling	p. 328
Large-Scale Parallel Collaborative Filtering for the Netflix Prize	p. 337
Author Index	p. 349
Table of Contents provided by Blackwell. All Rights Reserved.