Kamesh Munagala's Research Interests

My main research interest is in algorithm design and theoretical computer science. I have worked on developing principled models and algorithms for various application domains: Scheduling and resource allocation; Data mining; Large-scale computing; Societal decision making; Computational economics, and so on. My work builds on 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.

I have placed a few representative publications below, grouped by application domain, which give a sampling of my research interests and current directions. A complete list of my papers is available on DBLP and on Google Scholar.

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

Opinion Dynamics and Societal Decision Making

We develop 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 user experiments.

Fair Allocations and Algorithmic Applications

We develop models for fair allocation of resources, and polynomial time algoirthms for finding these allocations. We show applications of such algorithms for scheduling in data centers and multi-core architectures, as well as in social choice.

Pricing and Auction Design

We develop approximation algorithms and mechanisms for auction design and pricing problems with side-constraints, such as budgets and externalities. More recently, we have been developing models and algorithms for pricing in two-sided marketplaces.

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.

Clustering and Network Design

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

Algorithms for Efficient Data Processing

We develop efficient algorithms in various large-scale computing models -- parallel and distributed computing, sensor networks, continuous query optimization (data streams), and I/O efficiency.

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.