Algorithms - ESA 2003: 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings

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 -