Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 7 Issue 3, July 2011

Minimizing movement in mobile facility location problems
Zachary Friggstad, Mohammad R. Salavatipour
Article No.: 28
DOI: 10.1145/1978782.1978783

In the mobile facility location problem, which is a variant of the classical facility location, each facility and client is assigned to a start location in a metric graph and our goal is to find a destination node for each client and...

How well can primal-dual and local-ratio algorithms perform?
Allan Borodin, David Cashman, Avner Magen
Article No.: 29
DOI: 10.1145/1978782.1978784

We define an algorithmic paradigm, the stack model, that captures many primal-dual and local-ratio algorithms for approximating covering and packing problems. The stack model is defined syntactically and without any complexity limitations and...

S-T connectivity on digraphs with a known stationary distribution
Kai-Min Chung, Omer Reingold, Salil Vadhan
Article No.: 30
DOI: 10.1145/1978782.1978785

We present a deterministic logspace algorithm for solving S-T Connectivity on directed graphs if: (i) we are given a stationary distribution of the random walk on the graph in which both of the input vertices s and t have...

Routing (un-) splittable flow in games with player-specific affine latency functions
Martin Gairing, Burkhard Monien, Karsten Tiemann
Article No.: 31
DOI: 10.1145/1978782.1978786

In this work we study weighted network congestion games with player-specific latency functions where selfish players wish to route their traffic through a shared network. We consider both the case of splittable and unsplittable traffic. Our main...

Rate vs. buffer size--greedy information gathering on the line
Adi Rosén, Gabriel Scalosub
Article No.: 32
DOI: 10.1145/1978782.1978787

We consider packet networks with limited buffer space at the nodes, and are interested in the question of maximizing the number of packets that arrive to destination rather than being dropped due to full buffers.

We initiate a more refined...

Minimizing flow time in the wireless gathering problem
Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela, Leen Stougie
Article No.: 33
DOI: 10.1145/1978782.1978788

We address the problem of efficient data gathering in a wireless network through multihop communication. We focus on two objectives related to flow times, that is, the times spent by data packets in the system: minimization of the maximum flow...

Randomized rendezvous with limited memory
Evangelos Kranakis, Danny Krizanc, Pat Morin
Article No.: 34
DOI: 10.1145/1978782.1978789

We present a trade-off between the expected time for two identical agents to rendezvous on a synchronous, anonymous, oriented ring and the memory requirements of the agents. In particular, we show there exists a 2t state agent which can...

Max-coloring and online coloring with bandwidths on interval graphs
Sriram V. Pemmaraju, Rajiv Raman, Kasturi Varadarajan
Article No.: 35
DOI: 10.1145/1978782.1978790

Given a graph G = (V, E) and positive integral vertex weights w: VN, the max-coloring problem seeks to find a proper vertex coloring of G whose color classes C1,...

To fill or not to fill: The gas station problem
Samir Khuller, Azarakhsh Malekian, Julián Mestre
Article No.: 36
DOI: 10.1145/1978782.1978791

In this article we study several routing problems that generalize shortest paths and the traveling salesman problem. We consider a more general model that incorporates the actual cost in terms of gas prices. We have a vehicle with a given tank...

The optimality of the online greedy algorithm in carpool and chairman assignment problems
Don Coppersmith, Tomasz Nowicki, Giuseppe Paleologo, Charles Tresser, Chai Wah Wu
Article No.: 37
DOI: 10.1145/1978782.1978792

We study several classes of related scheduling problems including the carpool problem, its generalization to arbitrary inputs and the chairman assignment problem. We derive both lower and upper bounds for online algorithms solving these problems....

The tree inclusion problem: In linear space and faster
Philip Bille, Inge Li Gortz
Article No.: 38
DOI: 10.1145/1978782.1978793

Given two rooted, ordered, and labeled trees P and T the tree inclusion problem is to determine if P can be obtained from T by deleting nodes in T. This problem has recently been recognized as an important query...

Improved approximations for the hotlink assignment problem
Eduardo Laber, Marco Molinaro
Article No.: 39
DOI: 10.1145/1978782.1978794

Let G=(V,E) be a graph representing a Web site, where nodes correspond to pages and arcs to hyperlinks. In this context, hotlinks are defined as shortcuts (new arcs) added to Web pages of G in order to reduce the time...