Kamesh Munagala
Professor of Computer Science
Current Appointments & Affiliations
 Professor of Computer Science, Computer Science, Trinity College of Arts & Sciences 2016
Contact Information
 Box 90129, Computer Science Department, Durham, NC 277080129
 D205, LSRC, Research Drive, Durham, NC 27708
 (919) 6606598
 Background

Duke Appointment History
 Associate Professor of Computer Science, Computer Science, Trinity College of Arts & Sciences 2011  2016
 Director of Graduate Studies of Computer Science, Computer Science, Trinity College of Arts & Sciences 2012  2015
 Associate Director of Graduate Studies of the Master, Computer Science, Trinity College of Arts & Sciences 2014  2015
 Assistant Professor of Computer Science, Computer Science, Trinity College of Arts & Sciences 2004  2010
 Recognition

Awards & Honors
 Expertise

Subject Headings
 Publications & Artistic Works

Selected Publications

Conference Papers
 Goel, A, Krishnaswamy, AK, and Munagala, K. "Metric distortion of social choice rules: Lower bounds and fairness properties." June 20, 2017. Full Text
 Fain, B, Goel, A, Munagala, K, and Sakshuwong, S. "Sequential deliberation for social choice." January 1, 2017. Full Text
 Nath, A, Fox, K, Agarwal, PK, and Munagala, K. "Massively parallel algorithms for computing TIN DEMs and contour trees for large terrains." October 31, 2016. Full Text
 Im, S, Kulkarni, J, and Munagala, K. "Competitive analysis of constrained queueing systems." August 1, 2016. Full Text
 Agarwal, PK, Fox, K, Munagala, K, and Nath, A. "Parallel algorithms for constructing range and nearestneighbor searching data structures." June 15, 2016. Full Text
 Fain, B, Goel, A, and Munagala, K. "The core of the participatory budgeting problem." January 1, 2016. Full Text
 Im, S, Kulkarni, J, and Munagala, K. "Competitive Flow Time Algorithms for Polyhedral Scheduling." December 11, 2015. Full Text
 Cao, Q, Sirivianos, M, Yang, X, and Munagala, K. "Combating Friend Spam Using Social Rejections." January 1, 2015. Full Text
 Goel, A, Munagala, K, Sharma, A, and Zhang, H. "A note on modeling retweet cascades on Twitter." January 1, 2015. Full Text
 Das, A, Gollapudi, S, and Munagala, K. "Modeling opinion dynamics in social networks." January 1, 2014. Full Text
 Guha, S, and Munagala, K. "Stochastic regret minimization via Thompson Sampling." January 1, 2014.
 Guha, S, and Munagala, K. "Approximate Indexability and Bandit Problems with Concave Rewards and Delayed Feedback." Springer, 2013. Full Text
 Kulkarni, J, and Munagala, K. "Algorithms for CostAware Scheduling." Springer, 2012. Full Text
 Bhattacharya, S, Gollapudi, S, and Munagala, K. "Consideration set generation in commerce search." ACM, 2011. Full Text
 Guha, S, and Munagala, K. "Modeldriven optimization using adaptive probes." SIAM, 2007.
 Silberstein, A, Puggioni, G, Gelfand, A, Munagala, K, and Yang, J. "Suppression and failures in sensor networks: A Bayesian approach." January 1, 2007.
 Guha, S, Munagala, K, and Sarkar, S. "Approximation Schemes for Information Acquisition and Exploitation in Multichannel Wireless Networks." January 1, 2006.
 Srivastava, U, Munagala, K, Widom, J, and Motwani, R. "Query Optimization over Web Services." ACM, 2006.
 Guha, S, and Munagala, K. "Improved algorithms for the data placement problem." ACM/SIAM, 2002.
 Guha, S, and Munagala, K. "Generalized clustering." ACM/SIAM, 2002.
 Andrews, M, and Munagala, K. "Online Algorithms for Caching Multimedia Streams." Springer, 2000. Full Text

Journal Articles
 Sungjin, IM, Munagala, K, and Kulkarni, J. "Competitive algorithms from competitive equilibria: Nonclairvoyant scheduling under polyhedral constraints." Journal of the ACM 65, no. 1 (December 1, 2017). Full Text
 Kunjir, M, Fain, B, Munagala, K, and Babu, S. "ROBUS: Fair cache allocation for dataparallel workloads." Proceedings of the ACM SIGMOD International Conference on Management of Data Part F127746 (May 9, 2017): 219234. Full Text
 Bahmani, B, Goel, A, and Munagala, K. "Efficient primaldual graph algorithms for MapReduce." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8882 (January 1, 2014): 5978. Full Text
 Bhattacharya, S, Im, S, Kulkarni, J, and Munagala, K. "Coordination mechanisms from (almost) all scheduling policies." ITCS 2014  Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science (January 1, 2014): 121133. Full Text
 Im, S, Kulkarni, J, Munagala, K, and Pruhs, K. "SelfishMigrate: A scalable algorithm for nonclairvoyantly scheduling heterogeneous processors." Proceedings  Annual IEEE Symposium on Foundations of Computer Science, FOCS (January 1, 2014): 531540. Full Text
 Im, S, Kulkarni, J, and Munagala, K. "Competitive algorithms from competitive equilibria: Nonclairvoyant scheduling under polyhedral constraints." Proceedings of the Annual ACM Symposium on Theory of Computing (January 1, 2014): 313322. Full Text
 Munagala, K, and Xu, X. "Valuebased network externalities and optimal auction design." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8877 (January 1, 2014): 147160.
 Bhawalkar, K, Gollapudi, S, and Munagala, K. "Coevolutionary opinion formation games." Proceedings of the Annual ACM Symposium on Theory of Computing (2013): 4150. Full Text
 Bosagh Zadeh, R, Goel, A, Munagala, K, and Sharma, A. "On the precision of social and information networks." COSN 2013  Proceedings of the 2013 Conference on Online Social Networks (January 1, 2013): 6374. Full Text
 Bhalgat, A, Gollapudi, S, and Munagala, K. "Mechanisms and allocations with positive network externalities." Proceedings of the ACM Conference on Electronic Commerce (2012): 179196. Full Text
 Guha, S, and Munagala, K. "Adaptive uncertainty resolution in bayesian combinatorial optimization problems." ACM Transactions on Algorithms 8, no. 1 (2012). Full Text
 Manweiler, J, Santhapuri, N, Sen, S, Choudhury, RR, Nelakuditi, S, and Munagala, K. "Order matters: Transmission reordering in wireless networks." IEEE/ACM Transactions on Networking 20, no. 2 (2012): 353366. Full Text
 Ahmad, M, Aboulnaga, A, Babu, S, and Munagala, K. "Interactionaware scheduling of reportgeneration workloads." VLDB Journal 20, no. 4 (2011): 589615. Full Text
 Bhattacharya, S, Conitzer, V, and Munagala, K. "Approximation algorithm for security games with costly resources." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7090 LNCS (2011): 1324. Full Text
 Bhattacharya, S, Kulkarni, J, Munagala, K, and Xu, X. "On allocations with negative externalities." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7090 LNCS (2011): 2536. Full Text
 Haghpanah, N, Immorlica, N, Mirrokni, V, and Munagala, K. "Optimal auctions with positive network externalities." Proceedings of the ACM Conference on Electronic Commerce (2011): 1120. Full Text
 Zhang, Y, Munagala, K, and Yang, J. "Storing matrices on disk: Theory and practice revisited." Proceedings of the VLDB Endowment 4, no. 11 (2011): 10751086.
 Bhattacharya, S, Conitzer, V, Munagala, K, and Xia, L. "Incentive compatible budget elicitation in multiunit auctions." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (2010): 554572.
 Bhattacharya, S, Goel, G, Gollapudi, S, and Munagala, K. "Budget constrained auctions with heterogeneous items." Proceedings of the Annual ACM Symposium on Theory of Computing (2010): 379387. Full Text
 Conitzer, V, Immorlica, N, Letchford, J, Munagala, K, and Wagman, L. "Falsenameproofness in social networks." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6484 LNCS (2010): 209221. Full Text
 Goel, A, Guha, S, and Munagala, K. "How to probe for an extreme value." ACM Transactions on Algorithms 7, no. 1 (2010). Full Text
 Guha, S, Munagala, K, and Shi, P. "Approximation algorithms for restless bandit problems." Journal of the ACM 58, no. 1 (2010). Full Text
 Babu, S, Guha, S, and Munagala, K. "Largescale uncertainty management systems: Learning and exploiting your data." SIGMODPODS'09  Proceedings of the International Conference on Management of Data and 28th Symposium on Principles of Database Systems (2009): 995998. Full Text
 Duan, S, Babu, S, and Munagala, K. "Fa: A system for automating failure diagnosis." Proceedings  International Conference on Data Engineering (2009): 10121023. Full Text
 Goel, A, and Munagala, K. "Hybrid keyword search auctions." WWW'09  Proceedings of the 18th International World Wide Web Conference (2009): 221230. Full Text
 Guha, S, Meyerson, A, and Munagala, K. "A constant factor approximation for the single sink edge installation problem." SIAM Journal on Computing 38, no. 6 (2009): 24262442. Full Text
 Guha, S, Munagala, K, and Shi, P. "Approximation algorithms for restless bandit problems." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (2009): 2837.
 Guha, S, and Munagala, K. "Exceeding expectations and clustering uncertain data." Proceedings of the ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems (2009): 269277. Full Text
 Guha, S, and Munagala, K. "Multiarmed bandits with metric switching costs." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5556 LNCS, no. PART 2 (2009): 496507. Full Text
 Letchford, J, Conitzer, V, and Munagala, K. "Learning and approximating the optimal strategy to commit to." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5814 LNCS (2009): 250262. Full Text
 Manweiler, J, Santhapuri, N, Sen, S, Choudhury, RR, Nelakuditi, S, and Munagala, K. "Order matters: Transmission reordering in wireless networks." Proceedings of the Annual International Conference on Mobile Computing and Networking, MOBICOM (2009): 6172. Full Text
 Ahmad, M, Aboulanaga, A, Babu, S, and Munagala, K. "Modeling and exploiting query interactions in database systems." International Conference on Information and Knowledge Management, Proceedings (2008): 183192. Full Text
 Ahmad, M, Aboulnaga, A, Babu, S, and Munagala, K. "QShuffler: Getting the query mix right." Proceedings  International Conference on Data Engineering (2008): 14151417. Full Text
 Babu, S, Duan, S, and Munagala, K. "Processing diagnosis queries: A principled and scalable approach." Proceedings  International Conference on Data Engineering (2008): 14681470. Full Text
 Munagala, K, and Shi, P. "The stochastic machine replenishment problem." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5035 LNCS (2008): 169183. Full Text
 Flikkema, PG, Agarwal, PK, Clark, JS, Ellis, C, Gelfand, A, Munagala, K, and Yang, J. "From data reverence to data relevance: Modelmediated wireless sensing of the physical environment." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4487 LNCS (2007): 988994.
 Guha, S, Munagala, K, and Sarkar, S. "Jointly optimal transmission and probing strategies for multichannel wireless systems." 2006 IEEE Conference on Information Sciences and Systems, CISS 2006  Proceedings (2007): 955960. Full Text
 Guha, S, and Munagala, K. "Approximation algorithms for partialinformation based stochastic control with Markovian rewards." Proceedings  Annual IEEE Symposium on Foundations of Computer Science, FOCS (2007): 483493. Full Text
 Guha, S, and Munagala, K. "Approximation algorithms for budgeted learning problems." Proceedings of the Annual ACM Symposium on Theory of Computing (2007): 104113. Full Text
 Munagala, K, Srivastava, U, and Widom, J. "Optimization of continuous queries with shared expensive filters." Proceedings of the ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems (2007): 215224. Full Text
 Silberstein, A, Braynard, R, Filpus, G, Puggioni, G, Gelfand, A, Munagala, K, and Yang, J. "Datadriven processing in sensor networks." CIDR 2007  3rd Biennial Conference on Innovative Data Systems Research (2007): 1021.
 Flikkema, PG, Agarwal, PK, Clark, JS, Ellis, C, Gelfand, A, Munagala, K, and Yang, J. "Modeldriven dynamic control of embedded wireless sensor networks." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3993 LNCS  III (2006): 409416. Full Text
 Goel, A, Guha, S, and Munagala, K. "Asking the right questions: Modeldriven optimization using probes." Proceedings of the ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems (2006): 203212. Full Text
 Guha, S, Munagala, K, and Sarkar, S. "Optimizing transmission rate in wireless channels using adaptive probes." Performance Evaluation Review 34, no. 1 (2006): 381382. Full Text
 Silberstein, A, Braynard, R, Ellis, C, Munagala, K, and Yang, J. "A samplingbased approach to optimizing topk queries in sensor networks." Proceedings  International Conference on Data Engineering 2006 (2006): 68. Full Text
 Silberstein, A, Munagala, K, and Yang, J. "Energyefficient monitoring of extreme values in sensor networks." Proceedings of the ACM SIGMOD International Conference on Management of Data (2006): 169180. Full Text
 Babu, S, Munagala, K, Widom, J, and Motwani, R. "Adaptive caching for continuous queries." Proceedings  International Conference on Data Engineering (2005): 118129. Full Text
 Munagala, K, Babu, S, Motwani, R, and Widom, J. "The pipelined set cover problem." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3363 LNCS (2005): 8398. Full Text
 Munagala, K, Yang, J, and Yu, H. "Online view maintenance under a responsetime constraint." Lecture Notes in Computer Science 3669 (2005): 677688.
 Srivastaya, U, Munagala, K, and Widom, J. "Operator placement for innetwork stream query processing." Proceedings of the ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems (2005): 250258.
 Munagala, K, Tibshirani, R, and Brown, PO. "Cancer characterization and feature set extraction by discriminative margin clustering. (Published online)" BMC Bioinformatics 5 (March 3, 2004): 21. Full Text Link to Item
 Arya, V, Garg, N, Khandekar, R, Meyerson, A, Munagala, K, and Pandit, V. "Local search heuristics for kmedian and facility location problems." SIAM Journal on Computing 33, no. 3 (2004): 544562. Full Text
 Babu, S, Motwani, R, Munagala, K, Nishizawa, I, and Widom, J. "Adaptive ordering of pipelined stream filters." Proceedings of the ACM SIGMOD International Conference on Management of Data (2004): 407418.
 Guha, S, Krishnan, S, Munagala, K, and Venkatasubramanian, S. "Application of the twosided depth test to CSG rendering." Proceedings of the Symposium on Interactive 3D Graphics (2003): 177180.
 Guha, S, Meyerson, A, and Munagala, K. "A constant factor approximation algorithm for the faulttolerant facility location problem." Journal of Algorithms 48, no. 2 (2003): 429440. Full Text
 Goel, A, and Munagala, K. "Extending greedy multicast routing to delay sensitive applications." Algorithmica (New York) 33, no. 3 (2002): 335352.
 Arya, V, Garg, N, Khandekar, R, Meyerson, A, Munagala, K, and Pandit, V. "Local search heuristics for kmedian and facility location problems." Conference Proceedings of the Annual ACM Symposium on Theory of Computing (2001): 2129.
 Guha, S, Meyerson, A, and Munagala, K. "Improved algorithms for fault tolerant facility location." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (2001): 636641.
 Guha, S, Meyerson, A, and Munagala, K. "A constant factor approximation for the single sink edge installation problem." Conference Proceedings of the Annual ACM Symposium on Theory of Computing (2001): 383388.
 Meyerson, A, Munagala, K, and Plotkin, S. "Web caching using access statistics." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (2001): 354363.
 Meyerson, A, Munagala, K, and Plotkin, S. "Designing networks incrementally." Annual Symposium on Foundations of Computer Science  Proceedings (2001): 406415.
 Goel, A, and Munagala, K. "Balancing Steiner trees and shortest path trees online." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (2000): 562563.
 Guha, S, Meyerson, A, and Munagala, K. "Hierarchical placement and network design problems." Annual Symposium on Foundations of Computer Science  Proceedings (2000): 603612.
 Meyerson, A, Munagala, K, and Plotkin, S. "COSTDISTANCE: Two metric network design." Annual Symposium on Foundations of Computer Science  Proceedings (2000): 624630.
 Munagala, K, and Ranade, A. "I/Ocomplexity of graph algorithms." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (1999): 687694.
 Bhalgat, A, Gollapudi, S, and Munagala, K. "Optimal Auctions via the Multiplicative Weight Method." Link to Item

Some information on this profile has been compiled automatically from Duke databases and external sources. (Our About page explains how this works.) If you see a problem with the information, please write to Scholars@Duke and let us know. We will reply promptly.