enter search term and/or author name
Finding shortest contractible and shortest separating cycles in embedded graphs
Article No.: 24
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
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
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
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
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...
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
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
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...
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
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...
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...
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
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
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
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...
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...
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...
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...