David Eppstein (Ed.):
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA.
ACM/SIAM 2002, ISBN 0-89871-513-X
13. SODA 2002:
San Francisco, CA, USA
: An 8/13-approximation algorithm for the asymmetric maximum TSP.
Harold N. Gabow
: An ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph.
: Dense point sets have sparse Delaunay triangulations: or "... but not too nasty".
: Faster approximation schemes for fractional multicommodity flow problems.
: Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits.
: Succinct representations of lcp information and improvements in the compressed suffix arrays.
: Edge dominating and hypomatchable sets.
: Algorithms for quantified Boolean formulas.
: Mixing time and long paths in graphs.
: Generating random factored numbers, easily.
Csaba D. Tóth
: Binary space partitions for line segments with a limited number of directions.
Timothy M. Chan
: Semi-online maintenance of geometric optima and measures.
: Computer assisted proof of optimal approximability results.
, Nick Meyer
: The wake up and report problem is time-equivalent to the firing squad synchronization problem.
: On semidefinite programming relaxations for graph coloring and vertex cover.
: Efficient pattern-matching with don't cares.
: Explicit constructions of selectors and related combinatorial structures, with applications.
Philip N. Klein
: Preprocessing an undirected planar network to enable fast approximate distance queries.
: A new algorithm for protein folding in the HP model.
: An optimal (expected time) algorithm for minimizing lab costs in DNA sequencing.
: A fully combinatorial algorithm for submodular function minimization.