Search ACM DL

Search Issue

enter search term and/or author name

**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 Ω(*n*log log_{S} *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* log^{2} *n*)-time algorithm

Philip N. Klein, Shay Mozes, Oren Weimann

Article No.: 30

DOI: 10.1145/1721837.1721846

We give an *O*(*n* log^{2} *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 C_{n} be a graph drawn uniformly at random from graphs in *C* that contain exactly *n* vertices. Denote by *b*(ℓ; C_{n}) the number of...

**A 4 k^{2} 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 4*k*^{2} 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...

**A fast algorithm to generate open meandric systems and meanders**

Bruce Bobier, Joe Sawada

Article No.: 42

DOI: 10.1145/1721837.1721858

An open meandric system is a planar configuration of acyclic curves crossing an infinite horizontal line in the plane such that the curves may extend in both horizontal directions. We present a fast, recursive algorithm to exhaustively generate...

**Periodicity testing with sublinear samples and space**

Funda Ergun, S. Muthukrishnan, Cenk Sahinalp

Article No.: 43

DOI: 10.1145/1721837.1721859

In this work, we are interested in periodic trends in long data streams in the presence of computational constraints. To this end; we present algorithms for discovering periodic trends in the combinatorial property testing model in a data stream...