Kamesh Munagala's Research Interests

My main research interest is in algorithm design and theoretical computer science. My focus is on designing algorithms when the inputs to the problem are uncertain. Such uncertainty arises in several settings:
My work builds techniques in approximation and online algorithms; uses linear programming and duality in the analysis of algorithms; and uses game-theoretic techniques combined with data analysis for appropriate modeling.

A complete list of my papers is available on DBLP and on Google Scholar. I have placed a few representative papers below 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 the US Army.

Slides and Videos

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, as well as for classical scheduling problems.

Data-driven Societal Dynamics

We develop optimization and game-theoretic models to reason about phenomena such as opinion formation, information flow, and preference aggregation in society. 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 and analytic bounds.

Stochastic Optimization and Bandit Problems

We develop approximation algorithms for large classes of stochastic optimization and control-theoretic problems, particularly the celebrated 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.