Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 42 Issue 5, Sept. 1995

Calculating normalization constants of closed queueing networks by numerically inverting their generating functions
Gagan L. Choudhury, Kin K. Leung, Ward Whitt
Pages: 935-970
DOI: 10.1145/210118.210122
A new algorithm is developed for calculating normalization constants (partition functions) and moments of product-form steady-state distributions of closed queuing networks and related models. The essential idea is to numerically invert the...

On the k-server conjecture
Elias Koutsoupias, Christos H. Papadimitriou
Pages: 971-983
DOI: 10.1145/210118.210128
We prove that the work function algorithm for the k-server problem has a competitive ratio at most 2k−1. Manasse et al. [1988] conjectured that the competitive ratio for the...

A theory of using history for equational systems with applications
Rakesh M. Verma
Pages: 984-1020
DOI: 10.1145/210118.210130
Implementation of programming language interpreters, proving theorem of the form A=B, implementation of abstract data types, and program optimization are all problems that can be reduced to the problem of finding a normal form for an expression...

Online tracking of mobile users
Baruch Awerbuch, David Peleg
Pages: 1021-1058
DOI: 10.1145/210118.210132
This paper deals with the problem of maintaining a distributed directory server, that enables us to keep track of mobile users in a distributed network. The paper introduces the graph-theoretic concept of regional matching, and...

Recoverable sequence transmission protocols
Ewan D. Tempero, Richard E. Ladner
Pages: 1059-1090
DOI: 10.1145/210118.210133
We consider the sequence transmission problem, that is, the problem of transmitting an infinite sequence of messages x1x2x3… over a channel that can both lose...

Eigenvalues and expansion of regular graphs
Nabil Kahale
Pages: 1091-1106
DOI: 10.1145/210118.210136
The spectral method is the best currently known technique to prove lower bounds on expansion. Ramanujan graphs, which have asymptotically optimal second eigenvalue, are the best-known explicit expanders. The spectral method yielded a lower bound...

A class of logic problems solvable by linear programming
Michele Conforti, Gérard Cornuéjols
Pages: 1107-1112
DOI: 10.1145/210118.210137
In propositional logic, several problems, such as satisfiability, MAX SAT and logical inference, can be formulated as integer programs. In this paper, we consider sets of clauses for which the corresponding integer programs can be solved as...