enter search term and/or author name
Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou
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
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
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
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
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
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
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...