Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 48 Issue 2, March 2001

Short proofs are narrow—resolution made simple
Eli Ben-Sasson, Avi Wigderson
Pages: 149-169
DOI: 10.1145/375827.375835
The widthof a Resolution proof is defined to be the maximal number of literals in any clause of the proof. In this paper, we relate proof width to proof length (=size), in both general Resolution, and its tree-like variant. The...

Improved master theorems for divide-and-conquer recurrences
Salvador Roura
Pages: 170-205
DOI: 10.1145/375827.375837
This paper presents new theorems to analyze divide-and-conquer recurrences, which improve other similar ones in several aspects. In particular, these theorems provide more information, free us almost completely from technicalities like floors...

Convex quadratic and semidefinite programming relaxations in scheduling
Martin Skutella
Pages: 206-242
DOI: 10.1145/375827.375840
We consider the problem of scheduling unrelated parallel machines subject to release dates so as to minimize the total weighted completion time of jobs. The main contribution of this paper is a provably good convex quadratic programming...

On-line analysis of the TCP acknowledgment delay problem
Daniel R. Dooly, Sally A. Goldman, Stephen D. Scott
Pages: 243-273
DOI: 10.1145/375827.375843
We study an on-line problem that is motivated by the networking problem of dynamically adjusting of acknowledgments in the Transmission Control Protocol (TCP). We provide a theoretical model for this problem in which the goal is to send acks at...

Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation
Kamal Jain, Vijay V. Vazirani
Pages: 274-296
DOI: 10.1145/375827.375845
We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is their low...

Concurrent threads and optimal parallel minimum spanning trees algorithm
Ka Wong Chong, Yijie Han, Tak Wah Lam
Pages: 297-323
DOI: 10.1145/375827.375847
This paper resolves a long-standing open problem on whether the concurrent write capability of parallel random access machine (PRAM) is essential for solving fundamental graph problems like connected components and minimum spanning trees in...

A general approach to dynamic packet routing with bounded buffers
Andrei Z. Broder, Alan M. Frieze, Eli Upfal
Pages: 324-349
DOI: 10.1145/375827.375849
We prove a sufficient condition for the stability of dynamic packet routing algorithms. Our approach reduces the problem of steady state analysis to the easier and better understood question of static routing. We show that certain high...