ACM DL

Algorithms (TALG)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Algorithms (TALG), Volume 13 Issue 1, December 2016

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 Max Bisection problem. We improve their algorithm to a 0.8776-approximation. As Max Bisection is hard to approximate...

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 rV and m monotone submodular functions f1, f2, …,...

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

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