ACM Transactions on Algorithms

We consider compact routing schemes in networks of low doubling dimension, where the doubling dimension is the least value α such that any ball in the network can be covered by at most 2^α balls of half radius. There are two variants of routing-scheme ...

Packet scheduling is a particular challenge in wireless networks due to interference from nearby transmissions. A distance-2 interference model serves as a useful abstraction here, and we study packet routing and scheduling under this model of ...

It is long known that for every weighted undirected n-vertex m-edge graph G = (V, E, ω), and every integer k ⩾ 1, there exists a ((2k − 1) · (1 + ϵ))-spanner with O(n^{1 + 1/k}) edges and weight O(k · n^1/k · ω(MST(G)), for an arbitrarily small constant ϵ > ...

Consider the following problem: given a graph with edge costs and a subset Q of vertices, find a minimum-cost subgraph in which there are two edge-disjoint paths connecting every pair of vertices in Q. The problem is a failure-resilient analog of the ...

The fastest known randomized algorithms for several parameterized problems use reductions to the k-MlD problem: detection of multilinear monomials of degree k in polynomials presented as circuits. The fastest known algorithm for k-MlD is based on 2^k ...

We study the streaming complexity and communication complexity of approximating unweighted semi-matchings. A semi-matching in a bipartite graph G = (A, B, E) with n = |A| is a subset of edges S⊆E that matches all A vertices to B vertices with the goal ...

Traditionally, the quality of orthogonal planar drawings is quantified by the total number of bends or the maximum number of bends per edge. However, this neglects that, in typical applications, edges have varying importance. We consider the problem O...

We give a new mathematical formulation of market equilibria in exchange economies using an indirect utility function: the function of prices and income that gives the maximum utility achievable. The formulation is a convex program and can be solved when ...

Assume that a group of n people is going to an excursion and our task is to seat them into buses with several constraints each saying that a pair of people does not want to see each other in the same bus. This is a well-known graph coloring problem (...

In this article, we consider the fault-tolerant k-median problem and give the first constant factor approximation algorithm for it. In the fault-tolerant generalization of the classical k-median problem, each client j needs to be assigned to at least r_j ...

We investigate the combinatorial complexity of geodesic Voronoi diagrams on polyhedral terrains using a probabilistic analysis. Aronov et al. [2008] prove that, if one makes certain realistic input assumptions on the terrain, this complexity is Θ(n+m√n) ...

We study a variant of the generalized assignment problem (gap), which we label all-or-nothing gap (agap). We are given a set of items, partitioned into n groups, and a set of m bins. Each item ℓ has size s_ℓ > 0, and utility a_ℓj ⩾ 0 if packed in bin j. ...

In this work, we present efficient algorithms for constructing sparse suffix trees, sparse suffix arrays, and sparse position heaps for b arbitrary positions of a text T of length n while using only O(b) words of space during the construction.

Attempts ...

The input to the NP-hard point line cover problem (PLC) consists of a set P of n points on the plane and a positive integer k; the question is whether there exists a set of at most k lines that pass through all points in P. By straightforward reduction ...

The field of exact exponential time algorithms for non-deterministic polynomial-time hard problems has thrived since the mid-2000s. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, non-trivial ...

We present a new approximation algorithm for the stochastic submodular set cover (SSSC) problem called adaptive dual greedy. We use this algorithm to obtain a 3-approximation algorithm solving the stochastic Boolean function evaluation (SBFE) problem ...

We revisit the traveling salesman problem with neighborhoods (TSPN) and propose several new approximation algorithms. These constitute either first approximations (for hyperplanes, lines, and balls in R^d, for d ⩾ 3) or improvements over previous ...

We present a new algorithm for computing the straight skeleton of a polygon. For a polygon with n vertices, among which r are reflex vertices, we give a deterministic algorithm that reduces the straight skeleton computation to a motorcycle graph ...