**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,...