Search ACM DL

Search Issue

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

DOI: 10.1145/2876055

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

DOI: 10.1145/2812811

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

DOI: 10.1145/2836167

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 ((2*k* − 1) · (1 +...

**The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs**

Glencora Borradaile, Philip Klein

Article No.: 30

DOI: 10.1145/2831235

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

DOI: 10.1145/2885499

The fastest known randomized algorithms for several parameterized problems use reductions to the *k*-M*k* in polynomials presented as circuits. The fastest known...

**Approximating Semi-matchings in Streaming and in Two-Party Communication**

Christian Konrad, Adi Rosén

Article No.: 32

DOI: 10.1145/2898960

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

DOI: 10.1145/2838736

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

**A Simple and Efficient Algorithm for Computing Market Equilibria**

Lisa Fleischer, Rahul Garg, Sanjiv Kapoor, Rohit Khandekar, Amin Saberi

Article No.: 34

DOI: 10.1145/2905372

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

DOI: 10.1145/2847419

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

**A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median**

Mohammadtaghi Hajiaghayi, Wei Hu, Jian Li, Shi Li, Barna Saha

Article No.: 36

DOI: 10.1145/2854153

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

DOI: 10.1145/2846099

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

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

DOI: 10.1145/2843944

We study a variant of the *generalized assignment problem* (*all-or-nothing* *n* groups, and a set of *m* bins....

**Sparse Text Indexing in Small Space**

Philip Bille, Johannes Fischer, Inge Li Gørtz, Tsvi Kopelowitz, Benjamin Sach, Hjalte Wedel Vildhøj

Article No.: 39

DOI: 10.1145/2836166

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

DOI: 10.1145/2832912

The input to the NP-hard *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...

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

DOI: 10.1145/2925416

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

DOI: 10.1145/2876506

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

DOI: 10.1145/2850418

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

**A Faster Algorithm for Computing Straight Skeletons**

Siu-Wing Cheng, Liam Mencel, Antoine Vigneron

Article No.: 44

DOI: 10.1145/2898961

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