Search ACM DL

Search Issue

enter search term and/or author name

**Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation**

Lukáš Poláček, Ola Svensson

Article No.: 13

DOI: 10.1145/2818695

The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et...

**A New Approach to Incremental Cycle Detection and Related Problems**

Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Robert E. Tarjan

Article No.: 14

DOI: 10.1145/2756553

We consider the problem of detecting a cycle in a directed graph that grows by arc insertions and the related problems of maintaining a topological order and the strong components of such a graph. For these problems, we give two algorithms, one...

**Anarchy Is Free in Network Creation**

Ronald Graham, Linus Hamilton, Ariel Levavi, Po-Shen Loh

Article No.: 15

DOI: 10.1145/2729978

The Internet has emerged as perhaps the most important network in modern computing, but rather miraculously, it was created through the individual actions of a multitude of agents rather than by a central planning authority. This motivates the...

**Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems**

Thomas Bläsius, Ignaz Rutter

Article No.: 16

DOI: 10.1145/2738054

In this article, we define and study the new problem of S

**Faster Spectral Sparsification and Numerical Algorithms for SDD Matrices**

Ioannis Koutis, Alex Levin, Richard Peng

Article No.: 17

DOI: 10.1145/2743021

We study algorithms for spectral graph sparsification. The input is a graph *G* with *n* vertices and *m* edges, and the output is a sparse graph *&Gtilde;* that approximates *G* in an algebraic sense. Concretely, for all...

**Optimal Partitioning for Dual-Pivot Quicksort**

Martin Aumüller, Martin Dietzfelbinger

Article No.: 18

DOI: 10.1145/2743020

*Dual-pivot quicksort* refers to variants of classical quicksort where in the partitioning step two pivots are used to split the input into three segments. This can be done in different ways, giving rise to different algorithms. Recently, a...

**Sorting and Selection with Imprecise Comparisons**

Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson

Article No.: 19

DOI: 10.1145/2701427

We consider a simple model of imprecise comparisons: there exists some δ > 0 such that when a subject is given two elements to compare, if the values of those elements (as perceived by the subject) differ by at least δ, then the...

**Improved Approximation Algorithms for Relay Placement**

Alon Efrat, Sándor P. Fekete, Joseph S. B. Mitchell, Valentin Polishchuk, Jukka Suomela

Article No.: 20

DOI: 10.1145/2814938

In the relay placement problem, the input is a set of sensors and a number *r* ⩾ 1, the communication range of a relay. In the *one-tier* version of the problem, the objective is to place a minimum number of relays so that between...

**Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions**

Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, Somnath Sikdar

Article No.: 21

DOI: 10.1145/2797140

We present a linear-time algorithm to compute a decomposition scheme for graphs *G* that have a set *X*⊆*V*(*G*), called a *treewidth-modulator*, such that the treewidth of *G* − *X* is bounded by a...

**Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension**

Ittai Abraham, Shiri Chechik, Cyril Gavoille, David Peleg

Article No.: 22

DOI: 10.1145/2818694

This article proposes a forbidden-set labeling scheme for the family of unweighted graphs with doubling dimension bounded by α. For an *n*-vertex graph *G* in this family, and for any desired precision parameter ε > 0, the...

**A Simplified 1.5-Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2**

Guy Kortsarz, Zeev Nutov

Article No.: 23

DOI: 10.1145/2786981

The Tree Augmentation Problem (TAP) is as follows: given a connected graph *G*=(*V*, *ϵ*) and an edge set *E* on *V*, find a minimum size subset of edges *F*⊆*E* such that (*V*,...

**The Minset-Poset Approach to Representations of Graph Connectivity**

Harold N. Gabow

Article No.: 24

DOI: 10.1145/2764909

Various instances of the minimal-set poset (minset-poset for short) have been proposed in the literature, e.g., the representation of Picard and Queyranne for all *st*-minimum cuts of a flow network. We begin with an explanation of why this...

**Label Cover Instances with Large Girth and the Hardness of Approximating Basic k-Spanner**

Michael Dinitz, Guy Kortsarz, Ran Raz

Article No.: 25

DOI: 10.1145/2818375

We study the well-known *Label Cover* problem under the additional requirement that problem instances have large girth. We show that if the girth is some *k*, the problem is roughly 2^{log 1-ε n)/k} hard to...

**Segmentation of Trajectories on Nonmonotone Criteria**

Boris Aronov, Anne Driemel, Marc Van Kreveld, Maarten Löffler, Frank Staals

Article No.: 26

DOI: 10.1145/2660772

In the trajectory segmentation problem, we are given a polygonal trajectory with *n* vertices that we have to subdivide into a minimum number of disjoint segments (subtrajectories) that all satisfy a given criterion. The problem is known to...