Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 3 Issue 3, August 2007

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 {(u1, u1), (u2, u2),…,(um, um)} 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 ue. 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 w1,w2,…,wn 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