Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 33 Issue 3, July 1986

Tuple sequences and lexicographic indexes
Serge Abiteboul, Seymour Ginsburg
Pages: 409-422
DOI: 10.1145/5925.5926
The concept of a tuple sequence is introduced in order to investigate structure connected with relational model implementation. Analogs are presented for the relational operations of projection, join, and selection, and the decomposition problem...

Elimination of intersection anomalies from database schemes
Catriel Beeri, Michael Kifer
Pages: 423-450
DOI: 10.1145/5925.5927
The desirability of acyclic (conflict-free) schemes is well argued in [8] and [13]. When a scheme is described by multivalued dependencies, acyclicity means that the dependencies do not split each other's left-hand side and do not form...

Security problems on inference control for SUM, MAX, and MIN queries
Francis Chin
Pages: 451-464
DOI: 10.1145/5925.5928

The basic inference problem is defined as follows: For a finite set X = {xi, … , xn}, we wish to infer properties of elements of X on the basis of sets of "queries" regarding subsets of X....

Sort sets in the relational model
Seymour Ginsburg, Richard Hull
Pages: 465-488
DOI: 10.1145/5925.5929
The notion of sort set is introduced here to formalize the fact that certain database relations can be sorted so that two or more columns are simultaneously listed in order. This notion is shown to be applicable in several ways...

A note on the height of binary search trees
Luc Devroye
Pages: 489-498
DOI: 10.1145/5925.5930
Let Hn be the height of a binary search tree with n nodes constructed by standard insertions from a random permutation of 1, … , n. It is shown that...

Reaching approximate agreement in the presence of faults
Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, William E. Weihl
Pages: 499-516
DOI: 10.1145/5925.5931
This paper considers a variant of the Byzantine Generals problem, in which processes start with arbitrary real values rather than Boolean values or values from some bounded range, and in which approximate, rather than exact, agreement is the...

Predicting fill for sparse orthogonal factorization
Thomas F. Coleman, Anders Edenbrandt, John R. Gilbert
Pages: 517-532
DOI: 10.1145/5925.5932
In solving large sparse linear least squares problems A x ≃ b, several different numeric methods involve computing the same upper triangular factor R of A. It is of interest to be able to...

A unified approach to approximation algorithms for bottleneck problems
Dorit S. Hochbaum, David B. Shmoys
Pages: 533-550
DOI: 10.1145/5925.5933
In this paper a powerful, and yet simple, technique for devising approximation algorithms for a wide variety of NP-complete problems in routing, location, and communication network design is investigated. Each of the algorithms presented here...

Improved methods for storing and updating information in the out-of-kilter algorithm
Samar Singh
Pages: 551-567
DOI: 10.1145/5925.5934
Currently, network codes based on the primal simplex algorithm are believed to be computationally superior to those based on other methods. Some modifications of the out-of-kilter algorithm of Ford and Fulkerson are given, together with proofs...

Asymptotic expansions for closed Markovian networks with state-dependent service rates
Debasis Mitra, J. McKenna
Pages: 568-592
DOI: 10.1145/5925.5935
A method is presented for calculating the partition function, and from it, performance measures, for closed Markovian stochastic networks with queuing centers in which the service or processing rate depends on the center's state or load. The...

The performance of a precedence-based queuing discipline
John N. Tsitsiklis, Christos H. Papadimitriou, Pierre Humblet
Pages: 593-602
DOI: 10.1145/5925.5936
A queuing system with infinitely many servers, and with the following queuing discipline is considered: For any two jobs i and j in the system, such that i arrived later than j,...

The polynomial-time hierarchy and sparse oracles
Jose L. Balcázar, Ronald V. Book, Uwe Schöning
Pages: 603-617
DOI: 10.1145/5925.5937
Questions about the polynomial-time hierarchy are studied. In particular, the questions, “Does the polynomial-time hierarchy collapse?” and “Is the union of the hierarchy equal to PSPACE?” are considered, along with...

Relativizing complexity classes with sparse oracles
Timothy J. Long, Alan L. Selman
Pages: 618-627
DOI: 10.1145/5925.5938
Baker, Gill, and Solovay constructed sparse sets A and B such that P(A) ≠ NP(A) and NP(B) ≠ co-NP(B). In contrast to their results, we...