ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 44 Issue 4, July 1997

Closure properties of constraints
Peter Jeavons, David Cohen, Marc Gyssens
Pages: 527-548
DOI: 10.1145/263867.263489
Many combinatorial search problems can be expressed as “constraint satisfaction problems” and this class of problems is known to be NP-complete in general. In this paper, we investigate the subclasses that arise from restricting the...

Constraint tightness and looseness versus local and global consistency
Peter van Beek, Rina Dechter
Pages: 549-566
DOI: 10.1145/263867.263499
Constraint networks are a simple representation and reasoning framework with diverse applications. In this paper, we identify two new complementary properties on the restrictiveness of the constraints in a network—constraint...

Approximating shortest paths on a convex polytope in three dimensions
Pankaj K. Agarwal, Sariel Har-Peled, Micha Sharir, Kasturi R. Varadarajan
Pages: 567-584
DOI: 10.1145/263867.263869
Given a convex polytope P with n faces in R3 , points s,t∈6P...

A simple min-cut algorithm
Mechthild Stoer, Frank Wagner
Pages: 585-591
DOI: 10.1145/263867.263872
We present an algorithm for finding the minimum cut of an undirected edge-weighted graph. It is simple in every respect. It has a short and compact description, is easy to implement, and has a surprisingly simple proof of correctness. Its...

Robust wait-free hierarchies
Prasad Jayanti
Pages: 592-614
DOI: 10.1145/263867.263888
The problem of implementing a shared object of one type from shared objects of other types has been extensively researched. Recent focus has mostly been on wait-free implementations, which permit every process to complete its...

Scale-sensitive dimensions, uniform convergence, and learnability
Noga Alon, Shai Ben-David, Nicolò Cesa-Bianchi, David Haussler
Pages: 615-631
DOI: 10.1145/263867.263927
Learnability in Valiant's PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free convergence property of means to expectations uniformly over classes of...

erratum: “ Two heads are better that two tapes”
Tao Jiang, Joel I. Seiferas, Paul M. B. Vitanyi
Page: 632
DOI: 10.1145/263867.268580