Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 51 Issue 4, July 2004

Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines
Luca Becchetti, Stefano Leonardi
Pages: 517-539
DOI: 10.1145/1008731.1008732
Scheduling a sequence of jobs released over time when the processing time of a job is only known at its completion is a classical problem in CPU scheduling in time sharing operating systems. A widely used measure for the responsiveness of the system...

Solving convex programs by random walks
Dimitris Bertsimas, Santosh Vempala
Pages: 540-556
DOI: 10.1145/1008731.1008733
Minimizing a convex function over a convex set in n-dimensional space is a basic, general problem with many interesting special cases. Here, we present a simple new algorithm for convex optimization based on sampling by a random walk. It...

The random oracle methodology, revisited
Ran Canetti, Oded Goldreich, Shai Halevi
Pages: 557-594
DOI: 10.1145/1008731.1008734
We take a critical look at the relationship between the security of cryptographic schemes in the Random Oracle Model, and the security of the schemes that result from implementing the random oracle by so called "cryptographic hash functions".The main...

Quantum lower bounds for the collision and the element distinctness problems
Scott Aaronson, Yaoyun Shi
Pages: 595-605
DOI: 10.1145/1008731.1008735
Given a function f as an oracle, the collision problem is to find two distinct indexes i and j such that f(i) = f(j), under the promise that such indexes exist. Since the security of many fundamental...

Approximating extent measures of points
Pankaj K. Agarwal, Sariel Har-Peled, Kasturi R. Varadarajan
Pages: 606-635
DOI: 10.1145/1008731.1008736
We present a general technique for approximating various descriptors of the extent of a set P of n points in Rd when the dimension d is an arbitrary fixed constant. For a given extent measure μ and a...

Edge-disjoint routing in plane switch graphs in linear time
Jan M. Hochstein, Karsten Weihe
Pages: 636-670
DOI: 10.1145/1008731.1008737
By a switch graph, we mean an undirected graph G = (PW, E) such that all vertices in P (the plugs) have degree one and all vertices in W (the switches) have even degrees. We...

A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
Mark Jerrum, Alistair Sinclair, Eric Vigoda
Pages: 671-697
DOI: 10.1145/1008731.1008738
We present a polynomial-time randomized algorithm for estimating the permanent of an arbitrary n × n matrix with nonnegative entries. This algorithm---technically a "fully-polynomial randomized approximation scheme"---computes an...