This book constitutes the refereed proceedings of the Second International Conference on Algorithmic Aspects in Information and Management, AAIM 2006, held in Hong Kong, China in June 2006.
The 34 revised full papers presented together with abstracts of 2 invited talks were carefully reviewed and selected from 263 submissions. The papers cover topics from areas such as online scheduling, game and finance, data structures and algorithms, computational geometry, optimization, graph, and string.
Author(s): Allan Borodin (auth.), Siu-Wing Cheng, Chung Keung Poon (eds.)
Series: Lecture Notes in Computer Science 4041 : Information Systems and Applications, incl. Internet/Web, and HCI
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2006
Language: English
Pages: 504
Tags: Algorithm Analysis and Problem Complexity; Data Structures; Discrete Mathematics in Computer Science; Numeric Computing; Probability and Statistics in Computer Science; Management/Business for Professionals
Front Matter....Pages -
Further Reflections on a Theory for Basic Algorithms....Pages 1-9
Algorithmic DNA Self-assembly....Pages 10-10
Online Scheduling on Parallel Machines with Two GoS Levels....Pages 11-21
Online Dial-A-Ride Problem with Time-Windows Under a Restricted Information Model....Pages 22-31
Online Scheduling with Hard Deadlines on Parallel Machines....Pages 32-42
Maximizing the Throughput of Multiple Machines On-Line....Pages 43-52
Lattice Embedding of Direction-Preserving Correspondence over Integrally Convex Set....Pages 53-63
Linear Programming Polytope and Algorithm for Mean Payoff Games....Pages 64-78
Atomic Routing Games on Maximum Congestion....Pages 79-91
Equilibrium Distribution of Advertising Prices....Pages 92-101
Finding Faithful Boyce-Codd Normal Form Decompositions....Pages 102-113
Instant Service Policy and Its Application to Deficit Round Robin....Pages 114-125
A Compression-Boosting Transform for Two-Dimensional Data....Pages 126-137
Non-metric Multicommodity and Multilevel Facility Location....Pages 138-148
Sublinear Time Width-Bounded Separators and Their Application to the Protein Side-Chain Packing Problem....Pages 149-160
Polygonal Curve Approximation Using Grid Points with Application to a Triangular Mesh Generation with Small Number of Different Edge Lengths....Pages 161-172
Distributions of Points and Large Convex Hulls of k Points....Pages 173-184
Throwing Stones Inside Simple Polygons....Pages 185-193
Some Basics on Tolerances....Pages 194-206
Note on a Class of Admission Control Policies for the Stochastic Knapsack Problem....Pages 207-219
Inverse Bottleneck Optimization Problems on Networks....Pages 220-230
An Efficient Algorithm for Evacuation Problems in Dynamic Network Flows with Uniform Arc Capacity....Pages 231-242
Connected Set Cover Problem and Its Applications....Pages 243-254
A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth....Pages 255-266
Recognition of Probe Cographs and Partitioned Probe Distance Hereditary Graphs....Pages 267-278
A New Approach for Solving the Maximum Clique Problem....Pages 279-290
The Approximability of the Exemplar Breakpoint Distance Problem....Pages 291-302
Computing the λ -Seeds of a String....Pages 303-313
Subsequence Packing: Complexity, Approximation, and Application....Pages 314-323
Decomposition Based Heuristic Approach to Frequency Reassignment Problem....Pages 324-333
Approximation Algorithms for Minimum Span Channel Assignment Problems....Pages 334-342
Weighted Broadcast in Linear Radio Networks....Pages 343-353
Secure Overlay Network Design....Pages 354-366
A Portfolio Selection Method Based on Possibility Theory....Pages 367-374
Branch on Price: A Fast Winner Determination Algorithm for Discount Auctions....Pages 375-386
Note on an Auction Procedure for a Matching Game in Polynomial Time....Pages 387-394
Back Matter....Pages -
