enter search term and/or author name
Scale-Free Compact Routing Schemes in Networks of Low Doubling Dimension
Goran Konjevod, Andréa W. Richa, Donglin Xia
Article No.: 27
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...
Distributed Algorithms for End-to-End Packet Scheduling in Wireless Ad Hoc Networks
V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan
Article No.: 28
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...
Fast Constructions of Lightweight Spanners for General Graphs
Michael Elkin, Shay Solomon
Article No.: 29
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 +...
The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs
Glencora Borradaile, Philip Klein
Article No.: 30
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...
LIMITS and Applications of Group Algebras for Parameterized Problems
Ioannis Koutis, Ryan Williams
Article No.: 31
The fastest known randomized algorithms for several parameterized problems use reductions to the k-M
Approximating Semi-matchings in Streaming and in Two-Party Communication
Christian Konrad, Adi Rosén
Article No.: 32
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...
Optimal Orthogonal Graph Drawing with Convex Bend Costs
Thomas Bläsius, Ignaz Rutter, Dorothea Wagner
Article No.: 33
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...
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...
Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Article No.: 35
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...
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...
On the Expected Complexity of Voronoi Diagrams on Terrains
Anne Driemel, Sariel Har-Peled, Benjamin Raichel
Article No.: 37
We investigate the combinatorial complexity of geodesic Voronoi diagrams on polyhedral terrains using a probabilistic analysis. Aronov et al.  prove that, if one makes certain realistic input assumptions on the terrain, this complexity is...
All-Or-Nothing Generalized Assignment with Application to Scheduling Advertising Campaigns
Ron Adany, Moran Feldman, Elad Haramaty, Rohit Khandekar, Baruch Schieber, Roy Schwartz, Hadas Shachnai, Tami Tamir
Article No.: 38
We study a variant of the generalized assignment problem (
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...
Point Line Cover: The Easy Kernel is Essentially Tight
Stefan Kratsch, Geevarghese Philip, Saurabh Ray
Article No.: 40
The input to the NP-hard
On Problems as Hard as CNF-SAT
Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström
Article No.: 41
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...
Approximation Algorithms for Stochastic Submodular Set Cover with Applications to Boolean Function Evaluation and Min-Knapsack
Amol Deshpande, Lisa Hellerstein, Devorah Kletenik
Article No.: 42
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...
The Traveling Salesman Problem for Lines, Balls, and Planes
Adrian Dumitrescu, Csaba D. Tóth
Article No.: 43
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 Rd, for d ⩾ 3) or...
A Faster Algorithm for Computing Straight Skeletons
Siu-Wing Cheng, Liam Mencel, Antoine Vigneron
Article No.: 44
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...