Journal of the Association for Computing Machinery articles

Recent articles from Journal of the Association for Computing Machinery

Short Proofs Are Narrow--Resolution Made Simple.(mathematical logic)
March 1, 2001... Abstract. The width of 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 following consequences of these relations reveal width...

Improved Master Theorems for Divide-and-Conquer Recurrences.
March 1, 2001... Abstract. 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 and ceilings, and cover a wider set of...

Convex Quadratic and Semidefinite Programming Relaxations in Scheduling.
March 1, 2001... Abstract. 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 relaxation of strongly polynomial size for...

On-Line Analysis of the TCP Acknowledgment Delay Problem.
March 1, 2001... Abstract. We study an on-line problem that is motivated by the networking problem of dynamically adjusting delays 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 times that minimize a linear...

Approximation Algorithms for Metric Facility Location and k-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation.
March 1, 2001... Abstract. 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 running time: O(m log m) and O(m log m(L + log(n)))...