Algorithms - ESA 2003 Book

	Sublinear Computing	1
	Authenticated Data Structures	2
	Approximation Algorithms and Network Games	6
	I/O-Efficient Structures for Orthogonal Range-Max and Stabbing-Max Queries	7
	Line System Design and a Generalized Coloring Problem	19
	Lagrangian Relaxation for the k-Median Problem: New Insights and Continuity Properties	31
	Scheduling for Flow-Time with Admission Control	43
	An Approximating a Geometric Prize-Collecting Travelling Salesman Problem with Time Windows	55
	Semi-clairvoyant Scheduling	67
	Algorithms for Graph Rigidity and Scene Analysis	78
	Optimal Dynamic Video-on-Demand Using Adaptive Broadcasting	90
	Multi-player and Multi-round Auctions with Severely Bounded Communication	102
	Network Lifetime and Power Assignment in ad hoc Wireless Networks	114
	Disjoint Unit Spheres Admit at Most Two Line Transversals	127
	An Optimal Algorithm for the Maximum-Density Segment Problem	136
	Estimating Dominance Norms of Multiple Data Streams	148
	Smoothed Motion Complexity	161
	Kinetic Dictionaries: How to Shoot a Moving Target	172
	Deterministic Rendezvous in Graphs	184
	Fast Integer Programming in Fixed Dimension	196
	Correlation Clustering - Minimizing Disagreements on Arbitrary Weighted Graphs	208
	Dominating Sets and Local Treewidth	221
	Approximating Energy Efficient Paths in Wireless Multi-hop Networks	230
	Bandwidth Maximization in Multicasting	242
	Optimal Distance Labeling for Interval and Circular-Arc Graphs	254
	Improved Approximation of the Stable Marriage Problem	266
	Fast Algorithms for Computing the Smallest k-Enclosing Disc	278
	The Minimum Generalized Vertex Cover Problem	289
	An Approximation Algorithm for MAX-2-SAT with Cardinality Constraint	301
	On-Demand Broadcasting Under Deadline	313
	Improved Bounds for Finger Search on a RAM	325
	The Voronoi Diagram of Planar Convex Objects	337
	Buffer Overflows of Merging Streams	349
	Improved Competitive Guarantees for QoS Buffering	361
	On Generalized Gossiping and Broadcasting	373
	Approximating the Achromatic Number Problem on Bipartite Graphs	385
	Adversary Immune Leader Election in ad hoc Radio Networks	397
	Universal Facility Location	409
	A Method for Creating Near-Optimal Instances of a Certified Write-All Algorithm	422
	I/O-Efficient Undirected Shortest Paths	434
	On the Complexity of Approximating TSP with Neighborhoods and Related Problems	446
	A Lower Bound for Cake Cutting	459
	Ray Shooting and Stone Throwing	470
	Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs	482
	Binary Space Partition for Orthogonal Fat Rectangles	494
	Sequencing by Hybridization in Few Rounds	506
	Efficient Algorithms for the Ring Loading Problem with Demand Splitting	517
	Seventeen Lines and One-Hundred-and-One Points	527
	Jacobi Curves: Computing the Exact Topology of Arrangements of Non-singular Algebraic Curves	532
	Streaming Geometric Optimization Using Graphics Hardware	544
	An Efficient Implementation of a Quasi-polynomial Algorithm for Generating Hypergraph Transversals	556
	Experiments on Graph Clustering Algorithms	568
	More Reliable Protein NMR Peak Assignment via Improved 2-Interval Scheduling	580
	The Minimum Shift Design Problem: Theory and Practice	593
	Loglog Counting of Large Cardinalities	605
	Packing a Trunk	618
	Fast Smallest-Enclosing-Ball Computation in High Dimensions	630
	Automated Generation of Search Tree Algorithms for Graph Modification Problems	642
	Boolean Operations on 3D Selective Nef Complexes: Data Structure, Algorithms, and Implementation	654
	Fleet Assignment with Connection Dependent Ground Times	667
	A Practical Minimum Spanning Tree Algorithm Using the Cycle Property	679
	The Fractional Prize-Collecting Steiner Tree Problem on Trees	691
	Algorithms and Experiments for the Webgraph	703
	Finding Short Integral Cycle Bases for Cyclic Timetabling	715
	Slack Optimization of Timing-Critical Nets	727
	Multisampling: A New Approach to Uniform Sampling and Approximate Counting	740
	Multicommodity Flow Approximation Used for Exact Graph Partitioning	752
	A Linear Time Heuristic for the Branch Decomposition of Planar Graphs	765
	Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs	776
	Author Index	789