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