Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 47 Issue 4, July 2000

Divide-and-conquer approximation algorithms via spreading metrics
Guy Even, Joseph Seffi Naor, Satish Rao, Baruch Schieber
Pages: 585-616
DOI: 10.1145/347476.347478
We present a novel divide-and-conquer paradigm for approximating NP-hard graph optimization problems. The paradigm models graph optimization problems that satisfy two properties: First, a divide-and-conquer approach is applicable. Second, a...

Speed is as powerful as clairvoyance
Bala Kalyanasundaram, Kirk Pruhs
Pages: 617-643
DOI: 10.1145/347476.347479
We introduce resource augmentation as a method for analyzing online scheduling problems. In resource augmentation analysis the on-line scheduler is given more resources, say faster processors or more processors, than the adversary. We apply this...

Relational queries over interpreted structures
Michael Benedikt, Leonid Libkin
Pages: 644-680
DOI: 10.1145/347476.347477
We rework parts of the classical relational theory when the underlying domain is a structure with some interpreted operations that can be used in queries. We identify parts of the classical theory that go through 'as before' when interpreted...

Complexity of finite-horizon Markov decision process problems
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender
Pages: 681-720
DOI: 10.1145/347476.347480
Controlled stochastic systems occur in science engineering, manufacturing, social sciences, and many other cntexts. If the systems is modeled as a Markov decision process (MDP) and will run ad infinitum, the optimal control...

Orthologic and quantum logic: models and computational elements
J. P. Rawling, S. A. Selesnick
Pages: 721-751
DOI: 10.1145/347476.347481
Motivated by a growing need to understand the computational potential of quantum devices we suggest an approach to the relevant issues via quantum logic and its model theory. By isolating such notions as quantum parallelism and interference...

Balanced sequences and optimal routing
Eitan Altman, Bruno Gaujal, Arie Hordijk
Pages: 752-775
DOI: 10.1145/347476.347482
The objective pursued in this paper is two-fold. The first part addresses the following combinatorial problem: is it possible to construct an infinite sequence over n letters where each letter is distributed as...

A needed narrowing strategy
Sergio Antoy, Rachid Echahed, Michael Hanus
Pages: 776-822
DOI: 10.1145/347476.347484
The narrowing relation over terms constitutes the basis of the most important operational semantics of languages that integrate functional and logic programming paradigms. It also plays an important role in the definition of some algorithms of...