Kamesh Munagala's Research Interests
My main research interest is discrete optimization.
- Methodology: Approximation algorithms, Sequential decision theory, and Algorithmic game theory.
- Applications: E-commerce, Database query optimization, Data analysis, and Networks.
- In the past, I have also worked on DNA microarray analysis and I/O-efficient
algorithms, though I do not work on those topics any more.
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.
Some Recent Papers
Auction Design and Algorithmic Pricing
We study the computational complexity of optimal and efficient auction
design in several settings, mainly involving side-constraints such as
externalities, uncertain information, and budgets on payments. Our main
results are approximation algorithms that lead to simple auctions.
Pricing with Externalities:
Auctions with Uncertainty and Budgets:
Stochastic Optimization and Multi-armed Bandits
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.
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.