enter search term and/or author name
We present a new technique of universe reduction. Primary applications are the dictionary problem and the predecessor problem. We give several new results on static dictionaries in different computational models: the word RAM, the practical RAM,...
For a graph (V,E), existing compact linear formulations for the minimum cut problem require Θ(|V||E|) variables and constraints and can be interpreted as a composition of...
Optimal dynamic vertical ray shooting in rectilinear planar subdivisions
Yoav Giora, Haim Kaplan
Article No.: 28
We consider the dynamic vertical ray shooting problem against horizontal disjoint segments, that is, the task of maintaining a dynamic set S of n nonintersecting horizontal line segments in the plane under a query that reports the...
Squarepants in a tree: Sum of subtree clustering and hyperbolic pants decomposition
Article No.: 29
We provide efficient constant-factor approximation algorithms for the problems of finding a hierarchical clustering of a point set in any metric space, minimizing the sum of minimimum spanning tree lengths within each cluster, and in the...
We give approximation algorithms and inapproximability results for a class of movement problems. In general, these problems involve planning the coordinated motion of a large collection of objects (representing anything from a robot swarm or...
An O(n log n) approximation scheme for Steiner tree in planar graphs
Glencora Borradaile, Philip Klein, Claire Mathieu
Article No.: 31
We give a Polynomial-Time Approximation Scheme (PTAS) for the Steiner tree problem in planar graphs. The running time is O(n log n)....
Near-optimal algorithms for maximum constraint satisfaction problems
Moses Charikar, Konstantin Makarychev, Yury Makarychev
Article No.: 32
In this article, we present two approximation algorithms for the maximum constraint satisfaction problem with k variables in each constraint (MAX k-CSP).
Given a (1 − ϵ) satisfiable 2CSP our first algorithm finds...
Instability of FIFO in the permanent sessions model at arbitrarily small network loads
Article No.: 33
We show that for any r > 0, there is a network of First-In-First-Out servers and a fixed set of sessions such that:
—The network load is r with respect to the permanent sessions model with bounded arrivals....