ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 49 Issue 2, March 2002

Map graphs
Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou
Pages: 127-138
DOI: 10.1145/506147.506148
We consider a modified notion of planarity, in which two nations of a map are considered adjacent when they share any point of their boundaries (not necessarily an edge, as planarity requires). Such adjacencies define a map...

Polynomial-time approximation schemes for geometric min-sum median clustering
Rafail Ostrovsky, Yuval Rabani
Pages: 139-156
DOI: 10.1145/506147.506149
The Johnson--Lindenstrauss lemma states that n points in a high-dimensional Hilbert space can be embedded with small distortion of the distances into an O(log n) dimensional space by applying a random linear transformation....

On the closest string and substring problems
Ming Li, Bin Ma, Lusheng Wang
Pages: 157-171
DOI: 10.1145/506147.506150
The problem of finding a center string that is "close" to every given string arises in computational molecular biology and coding theory. This problem has two versions: the Closest String problem and the Closest Substring problem. Given a set of...

Timed regular expressions

Pages: 172-206
DOI: 10.1145/506147.506151
In this article, we define timed regular expressions, a formalism for specifying discrete behaviors augmented with timing information, and prove that its expressive power is equivalent to the timed automata of Alur and Dill. This result...

Understanding TCP Vegas: a duality model
Steven H. Low, Larry L. Peterson, Limin Wang
Pages: 207-235
DOI: 10.1145/506147.506152
We view congestion control as a distributed primal--dual algorithm carried out by sources and links over a network to solve a global optimization problem. We describe a multilink multisource model of the TCP Vegas congestion control mechanism. The...

How bad is selfish routing?
Tim Roughgarden, Éva Tardos
Pages: 236-259
DOI: 10.1145/506147.506153
We consider the problem of routing traffic to optimize the performance of a congested network. We are given a network, a rate of traffic between each pair of nodes, and a latency function for each edge specifying the time needed to traverse the edge...

Task assignment with unknown duration

Pages: 260-288
DOI: 10.1145/506147.506154
We consider a distributed server system and ask which policy should be used for assigning jobs (tasks) to hosts. In our server, jobs are not preemptible. Also, the job's service demand is not known a priori. We are particularly...