Search ACM DL

Search Issue

enter search term and/or author name

**Faster algorithms for sorting by transpositions and sorting by block interchanges**

Jianxing Feng, Daming Zhu

Article No.: 25

DOI: 10.1145/1273340.1273341

In this article, we present a new data structure, called the permutation tree, to improve the running time of sorting permutation by transpositions and sorting permutation by block interchanges. The existing 1.5-approximation algorithm for sorting...

**Constructing pairwise disjoint paths with few links**

Himanshu Gupta, Rephael Wenger

Article No.: 26

DOI: 10.1145/1273340.1273342

Let *P* be a simple polygon and let {(*u*_{1}, *u*′_{1}), (*u*_{2}, *u*′_{2}),…,(*u*_{m}, *u*′_{m})} be a set of *m* pairs...

**Multicommodity demand flow in a tree and packing integer programs**

Chandra Chekuri, Marcelo Mydlarz, F. Bruce Shepherd

Article No.: 27

DOI: 10.1145/1273340.1273343

We consider requests for capacity in a given tree network *T* = (*V*, *E*) where each edge *e* of the tree has some integer capacity *u*_{e}. Each request *f* is a node pair with an integer demand...

**Windows scheduling as a restricted version of bin packing**

Amotz Bar-Noy, Richard E. Ladner, Tami Tamir

Article No.: 28

DOI: 10.1145/1273340.1273344

Given is a sequence of *n* positive integers *w*_{1},*w*_{2},…,*w*_{n} that are associated with the items 1,2,…*n*, respectively. In the *windows scheduling* problem, the...

**Approximate parameterized matching**

Carmit Hazay, Moshe Lewenstein, Dina Sokol

Article No.: 29

DOI: 10.1145/1273340.1273345

Two equal length strings *s* and *s*′, over alphabets Σ_{s} and Σ_{s}′, *parameterize match* if there exists a bijection π : Σ_{s} →...

**Improved approximation results for the stable marriage problem**

Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa

Article No.: 30

DOI: 10.1145/1273340.1273346

The stable marriage problem has recently been studied in its general setting, where both ties and incomplete lists are allowed. It is NP-hard to find a stable matching of maximum size, while any stable matching is a maximal matching and thus...

**Nearest-neighbor-preserving embeddings**

Piotr Indyk, Assaf Naor

Article No.: 31

DOI: 10.1145/1273340.1273347

In this article we introduce the notion of nearest-neighbor-preserving embeddings. These are randomized embeddings between two metric spaces which preserve the (approximate) nearest-neighbors. We give two examples of such embeddings for Euclidean...

**Convergence time to Nash equilibrium in load balancing**

Eyal Even-Dar, Alex Kesselman, Yishay Mansour

Article No.: 32

DOI: 10.1145/1273340.1273348

We study the number of steps required to reach a pure Nash equilibrium in a load balancing scenario where each job behaves selfishly and attempts to migrate to a machine which will minimize its cost. We consider a variety of load balancing models,...

**Routing and scheduling in multihop wireless networks with time-varying channels**

Matthew Andrews, Lisa Zhang

Article No.: 33

DOI: 10.1145/1273340.1273349

We study routing and scheduling in *multihop wireless networks*. When data is transmitted from its source node to its destination node it may go through other wireless nodes as intermediate hops. The data transmission is *node...
*

*
Novel architectures for P2P applications: The continuous-discrete approach
Moni Naor, Udi Wieder
Article No.: 34
DOI: 10.1145/1273340.1273350
*

*We propose a new approach for constructing P2P networks based on a dynamic decomposition of a continuous space into cells corresponding to servers. We demonstrate the power of this approach by suggesting two new P2P architectures and various...
*

*
Problems column
Samir Khuller
Article No.: 35
DOI: 10.1145/1273340.1273351
*