Volume 30, Number 1, 2000
: On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof.
Volume 30, Number 2, 2000
: When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree.
Timothy M. Chan
: Random Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions.
Volume 30, Number 3, 2000
, Alek Vainshtein
: The General Structure of Edge-Connectivity of a Vertex Subset in a Graph and its Incremental Maintenance. Odd Case.
: The Computational Complexity to Evaluate Representations of General Linear Groups.
Volume 30, Number 4, 2000
Victor Y. Pan
: Parallel Complexity of Computations with General and Toeplitz-Like Matrices Filled with Integers and Extensions.
Volume 30, Number 5, 2000
, Vitaly Rubinovich
: A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction.
Martin E. Dyer
, Sandeep Sen
: Fast and Optimal Parallel Multidimensional Search in PRAMs with Applications to Linear Programming and Related Problems.
Volume 30, Number 6, 2000
: Dual-Issue Scheduling for Binary Trees with Spills and Pipelined Loads.
, Paul E. Kearney
, Ming Li
: A Polynomial Time Approximation Scheme for Inferring Evolutionary Trees from Quartet Topologies and Its Application.
: The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant.
, Rémy La
: Variable-Sized Bin Packing: Tight Absolute Worst-Case Performance Ratios for Four Approximation Algorithms.