Kamesh Munagala's Research Interests
My main research interest is algorithm design for emerging database and networking systems.
- My
current focus is on approximate policy design for stochastic decision
problems and its applications to mechanism design, database query
optimization and wireless networks.
- I have also worked on
approximation and online algorithms for network design and clustering
applications, on DNA microarray analysis, and on I/O-efficient
algorithms.
A complete list of my papers is available via DBLP. Below, I have placed a few representative papers that give a sampling of my research interests.
Multi-armed Bandit Problems
The multi-armed bandit problem
in stochastic decision theory models the key trade-off between
exploring the state space and exploiting the current best option.
Though this problem admits to an elegant efficient optimal policy known
as the Gittins index, it is well-known that such index policies become
increasingly sub-optimal in the presence of cost constraints,
time-varying uncertain information, blocking constraints, etc. We
present a generic solution technique that combines the efficiency of
index policies with provable performance guarantees.
Model-driven Optimization
We
present a general framework for optimizing combinatorial problems in
the presence of uncertain information that can be adaptively resolved
at a cost.
Auction Theory
We
present a simple mechanism for making bidders reveal their uncertainty
truthfully in keyword search auctions. We also extend the results to
repeated auctions under a simple model of uncertainty.
We
consider the problem of designing multi-unit auctions when bidders have
private budget constraints. We show that a natural yet
counter-intuitive auction due to Ausubel is not only truthful but also
Pareto-optimal and revenue optimal in this setting. The hard part,
surprisingly, is to show truthfulness. We also present the first
approximation results for revenue optimal
multi-item auctions when bidders have arbitrary demand and budget
constraints. Our mechanisms are surprisingly simple posted price
schemes.
Approximation Algorithms for Network Design
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). We develop general algorithmic
techniques to optimally aggregate demands under these constraints.
Clustering: Theory and Practice
The first paper shows that a simple local search heuristic achieves the best known approximation ratio of around 3 for k-medians
clustering. The second paper presents simple to implement constant
factor approximations for the stochastic version of the k-center
problem.
We
define a new similarity metric for clustering anomalous data, and
devise a fast agglomerative technique to cluster gene expression data
and faults in system execution traces.
I/O Efficient Algorithms
My first paper. We showed almost optimal running times in the I/O-model for graph connectivity.
Copyright Notice:
Since most of these papers are published, the copyright has been
transferred to the respective publishers. The following is ACM's
copyright notice; other publishers have similar ones.
Copyright
© 20xx by the Association for Computing Machinery, Inc. Permission to
make digital or hard copies of part or all of this work for personal or
classroom use is granted without fee provided that copies are not made
or distributed for profit or commercial advantage and that new copies
bear this notice and the full citation on the first page. Copyrights
for components of this work owned by others than ACM must be honored.
Abstracting with credit is permitted.