ACM Transactions on Algorithms

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 facility such that ...

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 hence our ...

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 nonnegligible probability mass ...

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

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 analysis of ...

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 time and ...

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

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₁, C₂, …, C_k, minimize ∑_i=1^k max_v ∈ Cⁱ w(v). This problem, restricted to interval graphs, ...

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

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

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 primitive in XML databases. Kilpeläinen ...

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 spent by users to reach their ...