Search ACM DL

Search Issue

enter search term and/or author name

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