Search ACM DL

Search Issue

enter search term and/or author name

**Inapproximability of the Multilevel Uncapacitated Facility Location Problem**

Ravishankar Krishnaswamy, Maxim Sviridenko

Article No.: 1

DOI: 10.1145/2907050

In this article, we present improved inapproximability results for the *k*-level uncapacitated facility location problem. In particular, we show that there is no polynomial time approximation algorithm with performance guarantee better than...

**Better Balance by Being Biased**: A 0.8776-Approximation for Max Bisection

Per Austrin, Siavosh Benabbas, Konstantinos Georgiou

Article No.: 2

DOI: 10.1145/2907052

Recently, Raghavendra and Tan (SODA 2012) gave a 0.85-approximation algorithm for the M

**Nearest-Neighbor Searching Under Uncertainty II**

Pankaj K. Agarwal, Boris Aronov, Sariel Har-Peled, Jeff M. Phillips, Ke Yi, Wuzhou Zhang

Article No.: 3

DOI: 10.1145/2955098

Nearest-neighbor search, which returns the nearest neighbor of a query point in a set of points, is an important and widely studied problem in many fields, and it has a wide range of applications. In many of them, such as sensor databases,...

**Tabulating Pseudoprimes and Tabulating Liars**

Andrew Shallue

Article No.: 4

DOI: 10.1145/2957759

This article explores the asymptotic complexity of two problems related to the Miller-Rabin-Selfridge primality test. The first problem is to tabulate strong pseudoprimes to a single fixed base *a*. It is now proven that tabulating up to...

**An Improved Approximation Algorithm for the Edge-Disjoint Paths Problem with Congestion Two**

Ken-Ichi Kawarabayashi, Yusuke Kobayashi

Article No.: 5

DOI: 10.1145/2960410

In the maximum edge-disjoint paths problem, we are given a graph and a collection of pairs of vertices, and the objective is to find the maximum number of pairs that can be routed by edge-disjoint paths. An *r*-approximation algorithm for...

**Semi-Streaming Set Cover**

Yuval Emek, Adi Rosén

Article No.: 6

DOI: 10.1145/2957322

This article studies the set cover problem under the semi-streaming model. The underlying set system is formalized in terms of a hypergraph *G* = (*V*, *E*) whose edges arrive one by one, and the goal is to construct an edge...

**On the Tradeoff between Stability and Fit**

Edith Cohen, Graham Cormode, Nick Duffield, Carsten Lund

Article No.: 7

DOI: 10.1145/2963103

In computing, as in many aspects of life, changes incur cost. Many optimization problems are formulated as a one-time instance starting from scratch. However, a common case that arises is when we already have a set of prior assignments and must...

**How Good Is Multi-Pivot Quicksort?**

Martin Aumüller, Martin Dietzfelbinger, Pascal Klaue

Article No.: 8

DOI: 10.1145/2963102

*Multi-Pivot Quicksort* refers to variants of classical quicksort where in the partitioning step *k* pivots are used to split the input into *k* + 1 segments. For many years, multi-pivot quicksort was regarded as impractical, but in...

**2-Edge Connectivity in Directed Graphs**

Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, Nikos Parotsidis

Article No.: 9

DOI: 10.1145/2968448

Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of undirected graphs, surprisingly, not much has been investigated for directed graphs. In this article, we study 2-edge...

**Smoothed Analysis of the 2-Opt Algorithm for the General TSP**

Matthias Englert, Heiko Röglin, Berthold Vöcking

Article No.: 10

DOI: 10.1145/2972953

2-Opt is a simple local search heuristic for the traveling salesperson problem that performs very well in experiments with respect to both running time and solution quality. In contrast to this, there are instances on which 2-Opt may need an...

**Sparse Fault-Tolerant BFS Structures**

Merav Parter, David Peleg

Article No.: 11

DOI: 10.1145/2976741

A *fault-tolerant* structure for a network is required for continued functioning following the failure of some of the network’s edges or vertices. This article considers *breadth-first search (BFS)* spanning trees and addresses the...

**Waste Makes Haste**: Bounded Time Algorithms for Envy-Free Cake Cutting with Free Disposal

Erel Segal-Halevi, Avinatan Hassidim, Yonatan Aumann

Article No.: 12

DOI: 10.1145/2988232

We consider the classic problem of envy-free division of a heterogeneous good (“cake”) among several agents. It is known that, when the allotted pieces must be connected, the problem cannot be solved by a finite algorithm for three or...

**Minimum Latency Submodular Cover**

Sungjin Im, Viswanath Nagarajan, Ruben Van Der Zwaan

Article No.: 13

DOI: 10.1145/2987751

We study the Minimum Latency Submodular Cover (MLSC) problem, which consists of a metric (*V*, *d*) with source *r* ∈ *V* and *m* monotone submodular functions *f*_{1}, *f*_{2}, …,...

**Cheeger-Type Approximation for Sparsest st-Cut**

Robert Krauthgamer, Tal Wagner

Article No.: 14

DOI: 10.1145/2996799

We introduce the *st*-cut version of the sparsest-cut problem, where the goal is to find a cut of minimum sparsity in a graph *G*(*V*, *E*) among those separating two distinguished vertices *s*, *t* ∈ *V*....

**A New Approach to Online Scheduling**: Approximating the Optimal Competitive Ratio

Elisabeth Lübbecke, Olaf Maurer, Nicole Megow, Andreas Wiese

Article No.: 15

DOI: 10.1145/2996800

We propose a new approach to competitive analysis in online scheduling by introducing the novel concept of competitive-ratio approximation schemes. Such a scheme algorithmically constructs an online algorithm with a competitive ratio arbitrarily...

**Algorithms for Hub Label Optimization**

Maxim Babenko, Andrew V. Goldberg, Anupam Gupta, Viswanath Nagarajan

Article No.: 16

DOI: 10.1145/2996593

We consider the hub label optimization problem, which arises in designing fast preprocessing-based shortest-path algorithms. We give *O*(log *n*)-approximation algorithms for the objectives of minimizing the maximum label size...

**Lopsidependency in the Moser-Tardos Framework**: Beyond the Lopsided Lovász Local Lemma

David G. Harris

Article No.: 17

DOI: 10.1145/3015762

The Lopsided Lovász Local Lemma (LLLL) is a powerful probabilistic principle that has been used in a variety of combinatorial constructions. While this principle began as a general statement about probability spaces, it has recently been...