- An Experimental Analysis of Self-Adjusting Computation. [PDF]
(with Umut A. Acar, Guy E. Blelloch, Matthias Blume, and Robert Harper)
ACM Transactions on Programming Languages and Systems (TOPLAS), 2009, to appear
- Simpler Analyses of Local Search Algorithms for Facility
Location [PDF]
(with Anupam Gupta)
arXiv:0809.2554v1
We study local search algorithms
for metric instances of facility location problems. We give a proof
of the $k$-median result which avoids Arya et al.'s coupling
argument. We also show that for the problem of opening $k$
facilities $F$ to minimize the objective function $\Phi_p(F) =
\big(\sum_{j \in V} d(j, F)^p\big)^{1/p}$, the natural swap-based
local-search algorithm is a $\Theta(p)$-approximation.
- Robust Kinetic Convex Hulls in 3D [PDF]
(with Umut A. Acar, Guy E. Blelloch, and Duru Turkoglu)
ESA 2008
We apply advances on
self-adjusting computation to provide a robust motion simulation
technique that combines kinetic event-based scheduling and the
classic idea of fixed-time sampling. The idea is to divide time
into a lattice of fixed- size intervals, and process events at the
resolution of an interval. We apply the approach to the problem of
kinetic maintenance of convex hulls in 3D. The effectiveness of the
proposal was experimentally evaluated.
- All-Norms and All-L_p-Norms Approximation Algorithms
[PDF | Full PDF]
(with Daniel Golovin, Anupam Gupta, and Amit Kumar)
FSTTCS 2008
Tech Report CMU-CS-07-153
We examine approximation
algorithms that simultaneously perform well on all norms, or on all
L_p norms. We show that the greedy algorithm for set cover
simultaneously O(p) approximates the L_p norm of the cover time
vector for all values of p, and that no efficient algorithm can do
better than O(p) for any fixed value of p. We also present
algorithms and structural results for other problems such as
k-facility-location, TSP, and average flow-time minimization.
- Kinetic 3D convex hulls via self-adjusting computation
[PDF | Video]
(with Umut A. Acar and Guy E. Blelloch)
SOCG
2007
We illustrate a solution to
kinetic 3D convex hulls using self-adjusting computation. First
introduced by Basch, Guibas, and Hershberger, the kinetic approach
to motion simulations requires maintaining a data structure along
with a set of certificates: each certificate is a comparison
and its failure time (the time at which the outcome of the
comparison changes). To simulate motion, an event scheduler updates
the certificates in chronological order of their failure times and
invokes an update procedure that keeps the data structure
consistent with the certificates.
- Kinetic Algorithms Via Self-adjusting Computation
[PDF]
(with Umut A. Acar, Guy E. Blelloch, and Jorge L. Vittes)
ESA
2006
Define a static algorithm as an
algorithm that computes some combinatorial property of its input
consisting of static, i.e., non-moving, objects. In this paper, we
describe a technique for syntactically transforming static
algorithms into kinetic algorithms, which compute properties of
moving objects. The technique offers capabilities for composing
kinetic algorithms, for integrating dynamic and kinetic changes,
and for ensuring robustness even with fixed-precision
floating-point arithmetic. To evaluate the effectiveness of the
approach, we implement a library for performing the transformation,
transform a number of algorithms, and give an experimental
evaluation. The results show that the technique performs well in
practice.
- An experimental analysis of self-adjusting computation
[PDF]
(with Umut A. Acar, Guy E. Blelloch, and Matthias Blume)
PLDI
2006
Dependence graphs and memoization
can be used to efficiently update the output of a program as the
input changes dynamically. Recent work has studied techniques for
combining these approaches to effectively dynamize a wide range of
applications. Toward this end various theoretical results were
given. In this paper we describe the implementation of a library
based on these ideas, and present experimental results on the
efficiency of this library on a variety of applications. The
results of the experiments indicate that the approach is effective
in practice, often requiring orders of magnitude less time than
recomputing the output from scratch. We believe this is the first
experimental evidence that incremental computation of any type is
effective in practice for a reasonably broad set of
applications.
- A Library for Self-Adjusting Computation [PDF]
(with Umut A. Acar, Guy E. Blelloch, Matthias Blume, and Robert
Harper)
ML'05
We present a Standard ML library
for writing programs that automatically adjust to changes to their
data. The library combines modifiable references and memoization to
achieve efficient updates. We describe an implementation of the
library and apply it to the problem of maintaining the convex hull
of a dynamically changing set of points. Our experiments show that
the overhead of the library is small, and that self-adjusting
programs can adjust to small changes three-orders of magnitude
faster than recomputing from scratch. The implementation relies on
invariants that could be enforced by a modal type system. We show,
using an existing language, abstract interfaces for modifiable
references and for memoization that ensure the same safety
properties without the use of modal types. The interface for
memoization, however, does not scale well, suggesting a
language-based approach to be preferable after all.