Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 45 Issue 5, Sept. 1998

Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
Sanjeev Arora
Pages: 753-782
DOI: 10.1145/290179.290180
We present a polynomial time approximation scheme for Euclidean TSP in fixed dimensions. For every fixed c > 1 and given any n nodes in R...

Beyond the flow decomposition barrier
Andrew V. Goldberg, Satish Rao
Pages: 783-797
DOI: 10.1145/290179.290181
We introduce a new approach to the maximum flow problem. This approach is based on assigning arc lengths based on the residual flow value and the residual arc capacities. Our approach leads to an...

Object identity as a query language primitive
Serge Abiteboul, Paris C. Kanellakis
Pages: 798-842
DOI: 10.1145/290179.290182
We demonstrate the power of object identities (oids) as a database query language primitive. We develop an object-based data model, whose structural part generalizes most of the known complex-object data models: cyclicity is allowed in both its...

On the space complexity of randomized synchronization
Faith Fich, Maurice Herlihy, Nir Shavit
Pages: 843-862
DOI: 10.1145/290179.290183
The “waite-free hierarchy” provides a classification of multiprocessor synchronization primitives based on the values of n for which there are deterministic wait-free implementations of n-process...

Noise-tolerant distribution-free learning of general geometric concepts
Nader H. Bshouty, Sally A. Goldman, H. David Mathias, Subhash Suri, Hisao Tamaki
Pages: 863-890
DOI: 10.1145/290179.290184
We present an efficient algorithm for PAC-learning a very general class of geometric concepts over R d for fixed d. More specifically, let...