Search ACM DL

Search Issue

enter search term and/or author name

**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 2*t* 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*: *V* → **N**, the *max-coloring problem* seeks to find a proper vertex coloring of *G* whose color classes *C*_{1},...

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