Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 45 Issue 2, March 1998

How to learn an unknown environment. I: the rectilinear case
Xiaotie Deng, Tiko Kameda, Christos Papadimitriou
Pages: 215-245
DOI: 10.1145/274787.274788
We consider the problem faced by a robot that must explore and learn an unknown room with obstacles in it. We seek algorithms that achieve a bounded ratio of the worst-case distance traversed in order to see all visible points of the environment...

Approximate graph coloring by semidefinite programming
David Karger, Rajeev Motwani, Madhu Sudan
Pages: 246-265
DOI: 10.1145/274787.274791
We consider the problem of coloring k-colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm that colors a 3-colorable graph on n vertices with...

Computing homology groups of simplicial complexes in R3
Tamal K. Dey, Sumanta Guha
Pages: 266-287
DOI: 10.1145/274787.274810
Recent developments in analyzing molecular structures and representing solid models using simplicial complexes have further enhanced the need for computing structural information about simplicial complexes in...

Randomized binary search trees
Conrado Martínez, Salvador Roura
Pages: 288-323
DOI: 10.1145/274787.274812
In this paper, we present randomized algorithms over binary search trees such that: (a) the insertion of a set of keys, in any fixed order, into an initially empty tree always produces a random binary search tree; (b) the deletion of any key...

On contention resolution protocols and associated probabilistic phenomena
P. D. MacKenzie, C. G. Plaxton, R. Rajaraman
Pages: 324-378
DOI: 10.1145/274787.274816
Consider an on-line scheduling problem in which a set of abstract processes are competing for the use of a number of resources. Further assume that it is either prohibitively expensive or impossible for any two of the processes to directly...