ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 32 Issue 1, Jan. 1985

Three approaches to heuristic search in networks
A. Bagchi, A. Mahanti
Pages: 1-27
DOI: 10.1145/2455.2458
Three different approaches to heuristic search in networks are analyzed. In the first approach, as formulated initially by Hart, Nilsson, and Raphael, and later modified by Martelli, the basic idea is to choose for expansion that node for which...

AND/OR graph heuristic search methods
A. Mahanti, A. Bagchi
Pages: 28-51
DOI: 10.1145/2455.2459
Two new marking algorithms for AND/OR graphs called CF and CS are presented. For admissible heuristics CS is not needed, and CF is shown to be preferable to the marking algorithms of Martelli and Montanari. When the heuristic is not admissible,...

Synchronizing clocks in the presence of faults
Leslie Lamport, P. M. Melliar-Smith
Pages: 52-78
DOI: 10.1145/2455.2457
Algorithms are described for maintaining clock synchrony in a distributed multiprocess system where each process has its own clock. These algorithms work in the presence of arbitrary clock or process failures, including “two-faced...

Disaggregations in databases
Serge Abiteboul
Pages: 79-101
DOI: 10.1145/2455.2463
An algebraic foundation of database schema design is presented. A new database operator, namely, disaggregation, is introduced. Beginning with “free” families, repeated applications of disaggregation and three other operators...

Memory-constrained task scheduling on a network of dual processors
Ken Fuchs, Dennis Kafura
Pages: 102-129
DOI: 10.1145/2455.2456
One aspect of network design is the extent to which memory is shared among the processing elements. In this paper a model with limited sharing (only two processors connected to each memory) is analyzed and its performance compared with the...

Approximation schemes for covering and packing problems in image processing and VLSI
Dorit S. Hochbaum, Wolfgang Maass
Pages: 130-136
DOI: 10.1145/2455.214106
A unified and powerful approach is presented for devising polynomial approximation schemes for many strongly NP-complete problems. Such schemes consist of families of approximation algorithms for each desired performance bound on the relative...

Algebraic laws for nondeterminism and concurrency
Matthew Hennessy, Robin Milner
Pages: 137-161
DOI: 10.1145/2455.2460
Since a nondeterministic and concurrent program may, in general, communicate repeatedly with its environment, its meaning cannot be presented naturally as an input/output function (as is often done in the denotational approach to semantics). In...

Aggregation with an error of O(&egr;2)
Hendrik Vantilborgh
Pages: 162-190
DOI: 10.1145/2455.214107
An aggregative technique to obtain an improved approximation of the equilibrium vector of a Markov chain with a nearly completely decomposable transition matrix is presented. The technique is demonstrated on a model of a multiprogrammed computer...

Bounds on information exchange for Byzantine agreement
Danny Dolev, Rüdiger Reischuk
Pages: 191-204
DOI: 10.1145/2455.214112
Byzantine Agreement has become increasingly important in establishing distributed properties when errors may exist in the systems. Recent polynomial algorithms for reaching Byzantine Agreement provide us with feasible solutions for obtaining...

Hard-core theorems for complexity classes
Shimon Even, Alan L. Selmen, Yacov Yacobi
Pages: 205-217
DOI: 10.1145/2455.214111
Nancy Lynch proved that if a decision problem A is not solvable in polynomial time, then there exists an infinite recursive subset X of its domain on which the decision is almost everywhere complex. In this...

A tight bound for black and white pebbles on the pyramid
Maria M. Klawe
Pages: 218-228
DOI: 10.1145/2455.214115
Lengauer and Tarjan proved that the number of black and white pebbles needed to pebble the root of a tree is at least half the number of black pebbles needed to pebble the root. This result is extended to a larger class of acyclic directed...

Solving low-density subset sum problems
J. C. Lagarias, A. M. Odlyzko
Pages: 229-246
DOI: 10.1145/2455.2461
The subset sum problem is to decide whether or not the 0-l integer programming problem &Sgr;ni=l aixi = M,...