Kamesh Munagala's Research Interests

My main research interest is in algorithm design and theoretical computer science. I work on a broad range of optimization problems arising in various application domains, shifting focus periodically. Despite the diversity of applications, the underlying themes in my research are the same: The development of techniques in approximation and online algorithms; the use of linear programming and duality in the analysis of algorithms; and the use of game-theoretic techniques combined with data analysis for appropriate modeling.

A complete list of my papers is available on DBLP and on Google Scholar. Below, I have placed a few representative papers that give a sampling of my research interests. I have  grouped the papers by research area, roughly in reverse chronological order. Though many of these topics are not my main focus now, I still maintain interest in all of them.

Most of my research has been funded by NSF through various awards. Some of it has also been funded by the Sloan Foundation, Cisco, and ARO.

Multi-dimensional Scheduling

We develop new theoretical models, both optimization (online algorithms) and game-theoretic, and associated algorithms for scheduling in data centers and multi-core architectures.

Societal Dynamics

We develop game-theoretic models to explain dynamic phenomena such as opinion formation and information flow in social networks. We attempt to support the models by data analysis and experiments.

Auction Design and Algorithmic Pricing

We develop approximation algorithms and mechanisms for auction design problems with side-constraints, such as budgets and externalities. Our focus has largely been on Bayesian mechanisms.

Stochastic Optimization and Bandit Problems

We develop approximation algorithms for large classes of stochastic optimization and control-theoretic problems, particularly the notorious multi-armed bandit problems from sequential decision theory.

Continuous Query Optimization

We develop stochastic models and efficient algorithms for continuous query optimization problems arising in data stream systems. This work is closely related to stochastic optimization.

Network Design, Clustering, and Facility Location

We develop approximation algorithms for several fundamental problems arising in provisioning resources on a network. We also develop practical clustering algorithms for problems arising in gene expression analysis.

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.