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
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
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...
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
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
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...
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...
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...
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
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
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
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
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
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 2log 1-ε n)/k hard to...
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...