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