Bernard Chazelle (auth.), Giuseppe Di Battista, Uri Zwick (eds.)3540200649, 9783540200642
The 66 revised full papers presented were carefully reviewed and selected from 165 submissions. The scope of the papers spans the entire range of algorithmics from design and mathematical analysis issues to real-world applications, engineering, and experimental analysis of algorithms.
Table of contents :
Front Matter….Pages –
Sublinear Computing….Pages 1-1
Authenticated Data Structures….Pages 2-5
Approximation Algorithms and Network Games….Pages 6-6
I/O-Efficient Structures for Orthogonal Range-Max and Stabbing-Max Queries….Pages 7-18
Line System Design and a Generalized Coloring Problem….Pages 19-30
Lagrangian Relaxation for the k-Median Problem: New Insights and Continuity Properties….Pages 31-42
Scheduling for Flow-Time with Admission Control….Pages 43-54
On Approximating a Geometric Prize-Collecting Traveling Salesman Problem with Time Windows….Pages 55-66
Semi-clairvoyant Scheduling….Pages 67-77
Algorithms for Graph Rigidity and Scene Analysis….Pages 78-89
Optimal Dynamic Video-on-Demand Using Adaptive Broadcasting….Pages 90-101
Multi-player and Multi-round Auctions with Severely Bounded Communication….Pages 102-113
Network Lifetime and Power Assignment in ad hoc Wireless Networks….Pages 114-126
Disjoint Unit Spheres admit at Most Two Line Transversals….Pages 127-135
An Optimal Algorithm for the Maximum-Density Segment Problem….Pages 136-147
Estimating Dominance Norms of Multiple Data Streams….Pages 148-160
Smoothed Motion Complexity….Pages 161-171
Kinetic Dictionaries: How to Shoot a Moving Target….Pages 172-183
Deterministic Rendezvous in Graphs….Pages 184-195
Fast Integer Programming in Fixed Dimension….Pages 196-207
Correlation Clustering – Minimizing Disagreements on Arbitrary Weighted Graphs….Pages 208-220
Dominating Sets and Local Treewidth….Pages 221-229
Approximating Energy Efficient Paths in Wireless Multi-hop Networks….Pages 230-241
Bandwidth Maximization in Multicasting….Pages 242-253
Optimal Distance Labeling for Interval and Circular-Arc Graphs….Pages 254-265
Improved Approximation of the Stable Marriage Problem….Pages 266-277
Fast Algorithms for Computing the Smallest k -Enclosing Disc….Pages 278-288
The Minimum Generalized Vertex Cover Problem….Pages 289-300
An Approximation Algorithm for MAX-2-SAT with Cardinality Constraint….Pages 301-312
On-Demand Broadcasting Under Deadline….Pages 313-324
Improved Bounds for Finger Search on a RAM….Pages 325-336
The Voronoi Diagram of Planar Convex Objects….Pages 337-348
Buffer Overflows of Merging Streams….Pages 349-360
Improved Competitive Guarantees for QoS Buffering….Pages 361-372
On Generalized Gossiping and Broadcasting….Pages 373-384
Approximating the Achromatic Number Problem on Bipartite Graphs….Pages 385-396
Adversary Immune Leader Election in ad hoc Radio Networks….Pages 397-408
Universal Facility Location….Pages 409-421
A Method for Creating Near-Optimal Instances of a Certified Write-All Algorithm….Pages 422-433
I/O-Efficient Undirected Shortest Paths….Pages 434-445
On the Complexity of Approximating TSP with Neighborhoods and Related Problems….Pages 446-458
A Lower Bound for Cake Cutting….Pages 459-469
Ray Shooting and Stone Throwing….Pages 470-481
Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs….Pages 482-493
Binary Space Partition for Orthogonal Fat Rectangles….Pages 494-505
Sequencing by Hybridization in Few Rounds….Pages 506-516
Efficient Algorithms for the Ring Loading Problem with Demand Splitting….Pages 517-526
Seventeen Lines and One-Hundred-and-One Points….Pages 527-531
Jacobi Curves: Computing the Exact Topology of Arrangements of Non-singular Algebraic Curves….Pages 532-543
Streaming Geometric Optimization Using Graphics Hardware….Pages 544-555
An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals….Pages 556-567
Experiments on Graph Clustering Algorithms….Pages 568-579
More Reliable Protein NMR Peak Assignment via Improved 2-Interval Scheduling….Pages 580-592
The Minimum Shift Design Problem: Theory and Practice….Pages 593-604
Loglog Counting of Large Cardinalities….Pages 605-617
Packing a Trunk….Pages 618-629
Fast Smallest-Enclosing-Ball Computation in High Dimensions….Pages 630-641
Automated Generation of Search Tree Algorithms for Graph Modification Problems….Pages 642-653
Boolean Operations on 3D Selective Nef Complexes: Data Structure, Algorithms, and Implementation….Pages 654-666
Fleet Assignment with Connection Dependent Ground Times….Pages 667-678
A Practical Minimum Spanning Tree Algorithm Using the Cycle Property….Pages 679-690
The Fractional Prize-Collecting Steiner Tree Problem on Trees….Pages 691-702
Algorithms and Experiments for the Webgraph….Pages 703-714
Finding Short Integral Cycle Bases for Cyclic Timetabling….Pages 715-726
Slack Optimization of Timing-Critical Nets….Pages 727-739
Multisampling: A New Approach to Uniform Sampling and Approximate Counting….Pages 740-751
Multicommodity Flow Approximation Used for Exact Graph Partitioning….Pages 752-764
A Linear Time Heuristic for the Branch-Decomposition of Planar Graphs….Pages 765-775
Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs….Pages 776-787
Back Matter….Pages –
Reviews
There are no reviews yet.