enter search term and/or author name
Minimizing movement in mobile facility location problems
Zachary Friggstad, Mohammad R. Salavatipour
Article No.: 28
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
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
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
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
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
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...
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
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 C1,...
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
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
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
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...