Multi-armed Bandit Problems
We present
approximation algorithms for fundamental, yet intractable, variants of
the
colorfully named multi-armed
bandit problem in stochastic decision theory. These
problems arise in scheduling under cost constraints, time-varying uncertain information, internet auctions, and other related contexts.
Approximation algorithms for restless bandit problems (with Sudipto Guha and Peng Shi) Submitted, 2008.
Sequential design of experiments via linear programming (with S. Guha) Full version of STOC '07 paper.
Model-driven Optimization
We develop a general
framework for optimizing combinatorial problems in the presence of
uncertain information that can be adaptively resolved at a cost. We
present approximation algorithms for optimizing several types of
problems in the presence of a costs on the uncertainty
resolution. We classify the results in terms of the type of the
underlying combinatorial optimization problem:
Packing, Scheduling, Geometric problems:
We
study several extensions to the canonical "quiz problem" that arise in
continuous query optimization in data stream and web service management
systems, and present exact and approximation
algorithms.
Optimization of continuous queries with shared expensive filters (w/ U. Srivastava J. Widom) PODS '07.
Operator placement for
in-network stream query processing (with U.
Srivastava
and J.
Widom) PODS '05.
Energy-efficient Monitoring Algorithms for Sensor Networks
We are considering
the problem of monitoring query results over node values in a sensor
network. The goal
is to design optimal control schemes to minimize transmission cost.
These algorithms are being implemented in the ecological sensor network
deployment in the Duke forest.
Optimizing top-k queries in sensor networks (with A. Silberstein, R. Braynard, C. Ellis, J.Yang) ICDE '06.
Optimizing top-k queries in sensor networks (with A. Silberstein, R. Braynard, C. Ellis, J.Yang) ICDE '06.
Approximation and Online Algorithms for Network
Design
In this body of
work, we present a
model for network design where resources like cables and routers need
to be allocated in a network to route given
demands to a core network or a
single
sink
node. The cost of allocating resources on an edge in
the network is modeled as a concave function of demand (this models economies
of scale).
Constant factor approximation for the single sink edge installation problem (w/ Guha, Meyerson) STOC '01.
I have also designed several online algorithms in the context of computer networks. The first two papers deal with designing networks when users arrive in an online fashion, and presents competitive algorithms for different objective functions.
I have also designed several online algorithms in the context of computer networks. The first two papers deal with designing networks when users arrive in an online fashion, and presents competitive algorithms for different objective functions.
Clustering and Facility Location
The main
result in
this body of work is the best approximation ratio for k-median clustering using a simple
local search algorithm. Other papers consider several variants of the
classical facility location
problem, to incorporate multiple types of demands, fault
tolerance, and
lower bounds on utilization of a facility.
Improved
algorithms for fault
tolerant facility location (with
Sudipto Guha and Adam
Meyerson)
SODA '01.
On
the integrality gap of capacitated facility location (w/ Z.
Abrams, A.
Meyerson, S.
Plotkin) 2002.
Cancer characterization and feature set extraction via discriminative margin clustering (with R. Tibshirani and P. O. Brown) BMC Bioinformatics 5:21, 2004.
Cancer characterization and feature set extraction via discriminative margin clustering (with R. Tibshirani and P. O. Brown) BMC Bioinformatics 5:21, 2004.
Miscellaneous Publications
Application
of the two-sided depth test to CSG rendering (with
S. Guha,
S. Krishnan, S. Venkat)
SI3D '03.