Algorithms (TALG)


Search Issue
enter search term and/or author name


ACM Transactions on Algorithms (TALG), Volume 6 Issue 2, March 2010

Editorial Note
Susanne Albers
Article No.: 22
DOI: 10.1145/1721837.1721838

Foreword to special issue SODA 2009
Claire Mathieu
Article No.: 23
DOI: 10.1145/1721837.1721839

Finding shortest contractible and shortest separating cycles in embedded graphs
Sergio Cabello
Article No.: 24
DOI: 10.1145/1721837.1721840

We give a polynomial-time algorithm to find a shortest contractible cycle (i.e., a closed walk without repeated vertices) in a graph embedded in a surface. This answers a question posed by Hutchinson. In contrast, we show that finding a shortest...

Approximate shared-memory counting despite a strong adversary
James Aspnes, Keren Censor
Article No.: 25
DOI: 10.1145/1721837.1721841

A new randomized asynchronous shared-memory data structure is given for implementing an approximate counter that can be incremented once by each of n processes in a model that allows up to n−1 crash failures. For any fixed...

Comparison-based time-space lower bounds for selection
Timothy M. Chan
Article No.: 26
DOI: 10.1145/1721837.1721842

We establish the first nontrivial lower bounds on time-space trade-offs for the selection problem. We prove that any comparison-based randomized algorithm for finding the median requires Ω(nlog logS n)...

Perfect matchings via uniform sampling in regular bipartite graphs
Ashish Goel, Michael Kapralov, Sanjeev Khanna
Article No.: 27
DOI: 10.1145/1721837.1721843

In this article we further investigate the well-studied problem of finding a perfect matching in a regular bipartite graph. The first nontrivial algorithm, with running time O(mn), dates back to König's work in 1916 (here...

Reasoning about online algorithms with weighted automata
Benjamin Aminof, Orna Kupferman, Robby Lampert
Article No.: 28
DOI: 10.1145/1721837.1721844

We describe an automata-theoretic approach for the competitive analysis of online algorithms. Our approach is based on weighted automata, which assign to each input word a cost in R≥0. By relating the “unbounded...

Approximating fractional hypertree width
Dániel Marx
Article No.: 29
DOI: 10.1145/1721837.1721845

Fractional hypertree width is a hypergraph measure similar to tree width and hypertree width. Its algorithmic importance comes from the fact that, as shown in previous work, Constraint Satisfaction Problems (CSP) and various problems in database...

Shortest paths in directed planar graphs with negative lengths: A linear-space O(n log2 n)-time algorithm
Philip N. Klein, Shay Mozes, Oren Weimann
Article No.: 30
DOI: 10.1145/1721837.1721846

We give an O(n log2 n)-time, linear-space algorithm that, given a directed planar graph with positive and negative arc-lengths, and given a node s, finds the distances from s to all nodes.

Maximal biconnected subgraphs of random planar graphs
Konstantinos Panagiotou, Angelika Steger
Article No.: 31
DOI: 10.1145/1721837.1721847

Let C be a class of labeled connected graphs, and let Cn be a graph drawn uniformly at random from graphs in C that contain exactly n vertices. Denote by b(ℓ; Cn) the number of...

A 4k2 kernel for feedback vertex set
Stéphan Thomassé
Article No.: 32
DOI: 10.1145/1721837.1721848

We prove that given an undirected graph G on n vertices and an integer k, one can compute, in polynomial time in n, a graph G′ with at most 4k2 vertices and an integer k′ such...

Discounted deterministic Markov decision processes and discounted all-pairs shortest paths
Omid Madani, Mikkel Thorup, Uri Zwick
Article No.: 33
DOI: 10.1145/1721837.1721849

We present algorithms for finding optimal strategies for discounted, infinite-horizon, Determinsitc Markov Decision Processes (DMDPs). Our fastest algorithm has a worst-case running time of O(mn), improving the recent bound of...

Efficient algorithms for the 2-gathering problem
Alon Shalita, Uri Zwick
Article No.: 34
DOI: 10.1145/1721837.1721850

Pebbles are placed on some vertices of a directed graph. Is it possible to move each pebble along at most one edge of the graph so that in the final configuration no pebble is left on its own? We give an O(mn)-time algorithm for...

Dynamic pricing for impatient bidders
Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rurda, Baruch Schieber, Maxim Sviridenko
Article No.: 35
DOI: 10.1145/1721837.1721851

We study the following problem related to pricing over time. Assume there is a collection of bidders, each of whom is interested in buying a copy of an item of which there is an unlimited supply. Every bidder is associated with a time interval...

Truthful unsplittable flow for large capacity networks
Yossi Azar, Iftah Gamzu, Shai Gutner
Article No.: 36
DOI: 10.1145/1721837.1721852

The unsplittable flow problem is one of the most extensively studied optimization problems in the field of networking. An instance of it consists of an edge capacitated graph and a set of connection requests, each of which is associated...

Facility location with hierarchical facility costs
Zoya Svitkina, ÉVA Tardos
Article No.: 37
DOI: 10.1145/1721837.1721853

We introduce a facility location problem with submodular facility cost functions, and give an O(log n) approximation algorithm for it. Then we focus on a special case of submodular costs, called hierarchical facility costs, and give...

Mechanism design for fractional scheduling on unrelated machines
George Christodoulou, Elias Koutsoupias, Annamária Kovács
Article No.: 38
DOI: 10.1145/1721837.1721854

Scheduling on unrelated machines is one of the most general and classical variants of the task scheduling problem. Fractional scheduling is the LP-relaxation of the problem, which is polynomially solvable in the nonstrategic setting, and is a...

Labeling schemes for vertex connectivity
Amos Korman
Article No.: 39
DOI: 10.1145/1721837.1721855

This article studies labeling schemes for the vertex connectivity function on general graphs. We consider the problem of assigning short labels to the nodes of any n-node graph is such a way that given the labels of any two nodes u...

Optimization problems in multiple-interval graphs
Ayelet Butman, Danny Hermelin, Moshe Lewenstein, Dror Rawitz
Article No.: 40
DOI: 10.1145/1721837.1721856

Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more then one interval associated with it. We initiate the study of optimization problems in multiple-interval graphs by considering three...

Dial a Ride from k-forest
Anupam Gupta, Mohammadtaghi Hajiaghayi, Viswanath Nagarajan, R. Ravi
Article No.: 41
DOI: 10.1145/1721837.1721857

The k-forest problem is a common generalization of both the k-MST and the dense-k-subgraph problems. Formally, given a metric space on n vertices V, with m demand pairs ⊆ V × V and...