Proc. 12th annual ACM-SIAM symposium on discrete algorithms (SIAM 2001)

SIAM9780898714906, 0898714907

Symposium held in Washington, DC, January 2001.
The Symposium was jointly sponsored by the SIAM Activity Group on Discrete Mathematics and by SIGACT, the ACM Special Interest Group on Algorithms and Computation Theory.
Contains 130 papers, which were selected based on originality, technical contribution, and relevance. Although the papers were not formally refereed, every attempt was made to verify the main claims. It is expected that most will appear in more complete form in scientific journals. The proceedings also includes the paper presented by invited plenary speaker Ronald Graham, as well as a portion of the papers presented by invited plenary speakers Udi Manber and Christos Papadimitriou.

---

Table of contents :
PROCEEDINGS OF THE TWELFTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS……Page 1
CONTENTS……Page 4
PREFACE……Page 14
ACKNOWLEDGMENTS……Page 15
Combinatorial approximation algorithms for the maximum directed cut problem……Page 16
ApproximationAlgorithms for the 0-Extension Problem……Page 23
A Faster Implementation of the Goemans-Williamson Clustering Algorithm……Page 32
Tree Packing and Approximating k-Cuts……Page 41
Generating Well-Shaped Delaunay Meshes in 3D……Page 43
Approximation algorithms for TSP with neighborhoods in the plane……Page 53
Dynamic Skin Triangulation*……Page 62
Online Point Location in Planar Arrangements and Its Applications*……Page 72
Reconciling Simplicity and Realism in Parallel Disk Models……Page 82
Distribution Sort with Randomized Cycling……Page 92
External Memory BFS on Undirected Graphs with Bounded Degree……Page 102
I/O-Efficient Algorithms for Graphs of Bounded Treewidth……Page 104
Constructing worst case instances for semidefinite programming based approximation algorithms……Page 107
Approximation Algorithms for the Metric Labeling Problem via a New Linear Programming Formulation……Page 124
Lattice Approximation and Linear Discrepancy of Totally Unimodular Matrices Extended Abstract……Page 134
On polynomial approximations to the shortest lattice vector length……Page 141
Approximation for Minimum Triangulation of Convex Polyhedra……Page 143
Optimal Covering Tours with Turn Costs……Page 153
Maintaining Approximate Extent Measures of Moving Points*……Page 163
Simplified Kinetic Connectivity for Rectangles and Hypercubes*……Page 173
Static and Kinetic Geometric Spanners with Applications……Page 183
Gossip is Synteny: Incomplete Gossip and an Exact Algorithm for Syntenic Distance……Page 192
Absolute Convergence:True Trees From Short Sequences……Page 201
Performance Study of Phylogenetic Methods:(Unweighted) Quartet Methods and Neighbor-Joining……Page 211
On the Midpath Tree Conjecture: A Counter-Example……Page 222
A probabilistic analysis of a greedy algorithm arising from computational biology……Page 223
Distance Labeling in Graphs* (Extended abstract)……Page 225
Steiner points in tree metrics don’t (really) help……Page 235
Fast Approximation of Centrality……Page 243
K-Pair Delay Constrained Minimum Cost Routing in Undirected Networks……Page 245
A Deterministic Algorithm for the COST-DISTANCE Problem……Page 247
Shape Sensitive Geometric Permutations*……Page 249
Geometric Permutations of High Dimensional Spheres*……Page 259
Inserting an Edge Into a Planar Graph……Page 261
Entropy-Preserving Cuttings and Space-Efficient Planar Point Location……Page 271
A Simple Entropy-Based Algorithm for Planar Point Location……Page 277
An experimental study of an opportunistic index……Page 284
Overlap Matching……Page 294
A Linear Lower Bound on Index Size for Text Retrieval……Page 304
Pattern Matching for Sets of Segments……Page 310
Approximate Subset Matching with Don’t Cares……Page 320
Dynamic String Searching……Page 322
On approximating the achromatic number……Page 324
Coloring k-colorable graphs using smaller palettes……Page 334
Approximating coloring and maximum independent sets in 3-uniform hypergraphs……Page 342
Improved Algorithms for 3-Coloring,3-Edge-Coloring, and Constraint Satisfaction……Page 344
Computing optimal -fat and -small decompositions……Page 353
Optimal Planar Point Location……Page 355
Polygonal Path Approximation with Angle Constraints……Page 357
Reconstructing a Collection of Curves with Corners and Endpoints……Page 359
Web Caching using Access Statistics……Page 369
Competitive On-Line Stream Merging Algorithms for Media-on-Demand……Page 379
On-line restricted caching……Page 389
Approximate Majorization and Fair Online Load Balancing……Page 399
Learning Markov Networks: Maximum Bounded Tree-Width Graphs……Page 407
Approximately Covering by Cycles in Planar Graphs……Page 417
Practical Approximation Algorithms for Zero- and Bounded-Skew Trees……Page 422
Approximating the Minimum Strongly Connected Subgraph via a Matching Lower Bound…….Page 432
Improved Approximation Algorithms for Rectangle Tiling and Packing……Page 442
Secure Notarization of Paper Text Documents……Page 452
Sublinear Time Approximate Clustering……Page 454
Efficient Oblivious Transfer Protocols……Page 463
Constructing Pseudo-Random Permutations with a Prescribed Structure……Page 473
Robust Algorithms for Restricted Domains……Page 475
Polynomial algorithms for partitioning problems on graphs with fixed clique-width (Extended abstract)……Page 483
A Polynomial Time Recognition Algorithm for Probe Interval Graphs……Page 492
Colored Tutte Polynomials and Kauffman Brackets for Graphs of Bounded Tree Width……Page 502
A New Constructive Root Bound for Algebraic Expressions……Page 511
Orderly Spanning Trees with Applications to Graph Encoding and Graph Drawing……Page 521
Alternatives to splay trees with O(log n) worst-case access times……Page 531
Worst Case Constant Time Priority Queue……Page 538
Representing Dynamic Binary Trees Succinctly……Page 544
Making Data Structures Confluently Persistent……Page 552
Compact labeling schemes for ancestor queries……Page 562
Better Approximation Algorithms for Bin Covering……Page 572
New Approaches to Covering and Packing Problems……Page 582
Parallel Processor Scheduling with Delay Constraints……Page 592
Approximation Algorithms for Extensible Bin Packing……Page 601
Scheduling Precedence-Constrained Jobs with Stochastic Processing Times on Parallel Machines……Page 604
Loss-Bounded Analysis for Differentiated Services…….Page 606
Stability Preserving Transformations: Packet Routing Networks with Edge Capacities and Speeds……Page 616
Distributed Admission Control, Scheduling, and Routing with Stale Information……Page 626
On Algorithms for Efficient Data Migration……Page 635
Fast distributed graph coloring with colors……Page 645
Improved Algorithms for Fault Tolerant Facility Location……Page 651
Algorithms for Facility Location Problems with Outliers……Page 657
The probabilistic relationship between the assignment and asymmetric traveling salesman problems……Page 667
Approximation Algorithms for Data Placement in Arbitrary Networks……Page 676
Polynomial-Time Approximation Schemes for Geometric Graphs……Page 686
Morphing between Polylines……Page 695
Fast Implementation of Depth Contours using Topological Sweep……Page 705
Computing the Depth of a Flat……Page 715
Which formulae shrink under random restrictions……Page 717
Selective Families, Superimposed Codes, and Broadcasting on Unknown Radio Networks……Page 724
Adversarial Models in Evolutionary Game Dynamics……Page 734
The Phase Transition in 1-in-k SAT and NAE 3-SAT……Page 736
Guessing secrets……Page 738
Can Entropy Characterize Performance of Online Algorithms?……Page 742
Competitive Auctions and Digital Goods……Page 750
Towards Understanding the Predictability of Stock Markets from the Perspective of Computational Complexity……Page 760
Performance Guarantee for Online Deadline Scheduling in the Presence of Overload……Page 770
Assigning chain-like tasks to a chain-like network……Page 780
Reductions Among High Dimensional Proximity Problems……Page 784
A cell probe lower bound for dynamic nearest-neighbour searching……Page 794
Shape matching using edit-distance: an implementation……Page 796
On Validating Planar Worlds……Page 806
Improved Fast Integer Sorting in Linear Space……Page 808
Single-Source Shortest-Paths on Arbitrary Directed Graphs in Linear Average-Case Time……Page 812
Optimal Constrained Graph Exploration……Page 822
An Efficient Algorithm for the Configuration Problem of Dominance Graphs……Page 830
Linear reductions of maximum matching……Page 840
Internet Packet Filter Management and Rectangle Geometry……Page 842
Faster Kinetic Heaps and Their Use in Broadcast Scheduling……Page 851
Finding Least Common Ancestors in Directed Acyclic Graphs……Page 860
On Binary Searching with Non-Uniform Costs……Page 870
Soft Kinetic Data Structures……Page 880
Testing graphs for colorability properties……Page 888
Random Lifts of Graphs……Page 898
Improved Results for Route Planning in Stochastic Transportation Networks……Page 910
Hill-climbing finds random planted bisections……Page 918
On Universally Easy Classes for NP-complete Problems……Page 925
The Diameter of Random Massive Graphs……Page 927
Domatic Partitions and the Lovasz Local Lemma……Page 937
Equitable Colorings Extend Chernoff-Hoeffding Bounds……Page 939
Universal Configurations in Light-Flipping Games……Page 941
On the discrete Bak-Sneppen model of self-organized cnticality……Page 943
AUTHOR INDEX……Page 950