Aravind Srinivasan's List of Publications

Some of the research reported below has been supported in part by the National Science Foundation, IARPA, the U.S. Army Research Office, and by Adobe, Amazon, and Google. I am grateful to these sources for their generous support. Any opinions, findings, and conclusions or recommendations expressed in these papers are those of the authors and do not necessarily reflect the views of these or any other institutions.

Copyright notice: Since most of these papers are published, the copyright has been transferred to the respective publishers. Therefore, the papers cannot be duplicated for commercial purposes. The following is ACM's copyright notice; other publishers have similar ones.

Copyright © 199x 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.

Please also note that the versions of the papers are mostly the final versions that I have, and may differ slightly from the published version.
I have annotated most papers with a partial list of keywords, using the following key:

AdW = Ad hoc/Wireless Networks ApA = Approximation Algorithms
Bio = Computational Biology DaS = Data Science
DiP = Distributed/Parallel Algorithms EC = E-Commerce and Game Theory
Fai = Fairness in Algorithms and in AI GrC = Graph/Hypergraph Coloring
InW = Internet/WWW-related KEx = Kidney/Organ Exchange
MLe = Machine Learning and Clustering PHe = Public Health
RaC = Randomness and Computation ReS = Resource Allocation and Scheduling
RoA = Routing Algorithms RoM = Rounding Methods in Integer Programming
SGr = Sustainable Growth SoN = Social Networks

Selected Publications

  1. Concentration of Submodular Functions and Read-k Families Under Negative Dependence, with S. Duppala, G. Li, J. Luque, and R. Valieva. To appear, Proc. Annual Symposium on Innovations in Theoretical Computer Science (ITCS), 2025. [Fai, RaC, ReS, RoM]

  2. Online Dependent Rounding Schemes for Bipartite Matchings, with Applications, with J. (Seffi) Naor and D. Wajc. To appear, Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025. (A mostly up-to-date version with a previous title.) [DaS, EC, Fai, PHe, RaC, ReS, RoM]

  3. Promoting External and Internal Equities under Ex-Ante/Ex-Post Metrics in Online Resource Allocation, with K. A. Sankararaman and P. Xu. Proc. International Conference on Machine Learning (ICML), 2024. (Spotlight Paper.) [DaS, Fai, PHe, RaC, ReS]

  4. Stochastic Optimization and Learning for Two-Stage Supplier Problems, with B. Brubach, N. Grammel, D. G. Harris, L. Tsepenekas, and A. Vullikanti. ACM Transactions on Probabilistic Machine Learning, accepted for publication. [ApA, DaS, MLe, PHe, RaC, ReS, RoM]

  5. Planning to Fairly Allocate: Probabilistic Fairness in the Restless Bandit Setting, with C. Herlihy, A. Prins, and J. P. Dickerson. Proc. ACM Conference on Knowledge Discovery and Data Mining (KDD), 732-740, 2023. (A preliminary version appeared in the Workshop on Responsible Decision Making in Dynamic Environments at the International Conference on Machine Learning (ICML), 2022.) [DaS, Fai, MLe, PHe, RaC]

  6. Flamingo: Environmental Impact Factor Matching for Life Cycle Assessment with Zero-Shot Machine Learning, with B. Balaji, G. Vunnava, N. Domingo, S. Gupta, H. Gupta, and G. Guest. ACM Journal on Computing and Sustainable Societies, Vol. 1, 1-23, 2023. [DaS, EC, MLe, SGr]

  7. Group Fairness in Set Packing Problems, with S. Duppala, J. Luque, and J. P. Dickerson. Proc. International Joint Conference on Artificial Intelligence (IJCAI), 391-399, 2023. Also accepted to the First Workshop on Computational Fair Division (CFD), co-located with IJCAI 2023. [DaS, Fai, KEx, RaC]

  8. Improved Bi-Point Rounding Algorithms and a Golden Barrier for k-median, with K. Gowda, T. Pensyl, and K. Trinh. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 987-1011, 2023. [ApA, MLe, RaC, RoM]

  9. Forecasting Patient Outcomes in Kidney Exchange, with N. Durvasula and J. P. Dickerson. (A fuller version is also available.) Proc. International Joint Conference on Artificial Intelligence (IJCAI-ECAI), pages 5052-5058, 2022. (AI for Good track.) [DaS, KEx, PHe]

  10. Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks, with A. Babay, M. Dinitz, L. Tsepenekas, and A. Vullikanti. Proc. International Conference on Artifical Intelligence and Statistics (AISTATS), pages 11641-11654, 2022. [ApA, DaS, MLe, PHe, RaC, ReS]

  11. A New Notion of Individually Fair Clustering: alpha-Equitable k-Center, with D. Chakrabarti, J. P. Dickerson, S. A. Esmaeili, and L. Tsepenekas. Proc. International Conference on Artifical Intelligence and Statistics (AISTATS), pages 6387-6408, 2022. [ApA, DaS, Fai, MLe, RaC]

  12. Dependent randomized rounding for clustering and partition systems with knapsack constraints, with D. G. Harris, T. Pensyl, and K. Trinh. Journal of Machine Learning Research (JMLR), 23(81), pages 1-41, 2022. Preliminary version in AISTATS 2020. [ApA, Fai, MLe, RaC, RoM]

  13. Deploying Vaccine Distribution Sites for Improved Accessibility and Equity to Support Pandemic Response, with G. Li, A. Li, M. V. Marathe, L. Tsepenekas, and A. Vullikanti. Proc. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 789-797, 2022. (Best Student Paper Award.) [ApA, DaS, Fai, MLe, PHe, ReS]

  14. Improved Guarantees for Offline Stochastic Matching via new Ordered Contention Resolution Schemes, with B. Brubach, N. Grammel, and W. Ma. Proc. Conference on Neural Information Processing Systems (NeurIPS), pages 27184-27195, 2021. [DaS, EC, RaC, ReS]

  15. Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints, with B. Brubach, D. Chakrabarti, J. P. Dickerson, and L. Tsepenekas. Proc. Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI), 2021. [ApA, Bio, DaS, Fai, MLe, PHe, RaC, ReS]

  16. Allocation Problems in Ride Sharing Platforms: Online Matching with Offline Reusable Resources, with J. P. Dickerson, K. A. Sankararaman, and P. Xu. ACM Transactions on Economics and Computation, Vol. 9, No. 3, pages 13:1-13:17, 2021. Preliminary version in AAAI 2018. [ApA, DaS, EC, KEx, PHe, RaC, ReS]

  17. A Pairwise Fair and Community-preserving Approach to k-center clustering, with B. Brubach, D. Chakrabarti, J. P. Dickerson, S. Khuller, and L. Tsepenekas. Proc. International Conference on Machine Learning (ICML), pages 1178-1189, 2020. [ApA, DaS, Fai, MLe, RaC, ReS]

  18. Meddling Metrics: the Effects of Measuring and Constraining Partisan Gerrymandering on Voter Incentives, with B. Brubach and S. Zhao. [DaS, Fai, ReS]

  19. The Moser-Tardos Framework with Partial Resampling, with D. G. Harris. Journal of the ACM, Vol. 66, pages 36:1-36:45, 2019. (This is a full version that combines our papers from STOC 2013 and FOCS 2013.) [ApA, InW, RaC, RoA, RoM]

  20. Approximation Algorithms for Stochastic Clustering, with D. G. Harris, S. Li, T. Pensyl, and K. Trinh. Journal of Machine Learning Research (JMLR), Vol. 20, No. 153, pages 1-33, 2019. A preliminary version appeared in Proc. Conference on Neural Information Processing Systems (NeurIPS), pages 6041-6050, 2018. [ApA, DaS, Fai, MLe, RaC, RoM]

  21. Algorithms to Approximate Column-Sparse Packing Problems, with B. Brubach, K. A. Sankararaman, and P. Xu. ACM Transactions on Algorithms, Vol. 16, pages 10:1-10:32, 2020. Preliminary version in SODA 2018. [ApA, RaC, RoM]

  22. Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines, with N. Bansal and O. Svensson. Proc. ACM Symposium on Theory of Computing (STOC), pages 156-167, 2016. Published online October 2019, special issue of SIAM Journal on Computing for STOC 2016. [ApA, RaC, ReS, RoM]

  23. A Constructive Lovász Local Lemma for Permutations, with D. G. Harris. Theory of Computing, Vol. 13, Article 17, pages 1-41, 2017. An earlier version appeared as "A Constructive Algorithm for the Lovász Local Lemma on Permutations" in the Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 907-925, 2014. [RaC]

  24. Approximation Algorithms for Throughput Maximization in Wireless Networks with Delay Constraints, with V. S. A. Kumar, S. Parthasarathy, and G. Pei. IEEE/ACM Transactions on Networking, Vol. 21, 1988-2000, 2013. (Supplementary material.) [AdW, ApA, RaC]

  25. New Constructive Aspects of the Lovász Local Lemma, with B. Haeupler and B. Saha. Journal of the ACM, Volume 58, Issue 6, 2011. [ApA, GrC, RaC]

  26. A Unified Approach to Scheduling on Unrelated Parallel Machines, with V. S. A. Kumar, M. V. Marathe, and S. Parthasarathy. Journal of the ACM, Vol. 56, 2009. [ApA, Fai, RaC, ReS, RoM]

  27. Efficient Lookup on Unstructured Topologies, with R. Morselli, B. Bhattacharjee, and M. Marsh. IEEE Journal on Selected Areas in Communications (Special Issue on Peer-to-Peer Communications and Applications), Vol. 25, pages 62-72, 2007. Full version with proofs (Technical Report CS-TR-4772, Department of Computer Science, University of Maryland, December 2005). [DiP, InW, RaC]

  28. An Extension of the Lovász Local Lemma, and its Applications to Integer Programming. SIAM Journal on Computing, Vol. 36, 609-634, 2006. [ApA, GrC, RaC, RoA, RoM]

  29. Dependent Rounding and its Applications to Approximation Algorithms, with R. Gandhi, S. Khuller, and S. Parthasarathy. Journal of the ACM, Vol. 53, 324-360, 2006. [ApA, RaC, RoM]

  30. Resilient Multicast using Overlays, with S. Banerjee, S. Lee, and B. Bhattacharjee. IEEE/ACM Transactions on Networking, Vol. 14, 237-248, 2006. [DiP, InW, RaC]

  31. Modelling Disease Outbreaks in Realistic Urban Social Networks, with S. Eubank, H. Guclu, V. S. A. Kumar, M. V. Marathe, Z. Toroczkai, and N. Wang. Nature, Vol. 429, 180-184, May 2004. (Supplemental Information) The same version is also available at Nature's website - subscription required. [DaS, PHe, RaC, SoN]

  32. Improved Bounds on the Sample Complexity of Learning, with Y. Li and P. M. Long. Journal of Computer and System Sciences, Vol. 62, 516-527, 2001. [MLe]

  33. The One-Inclusion Graph Algorithm is Near-Optimal for the Prediction Model of Learning, with Y. Li and P. M. Long. IEEE Transactions on Information Theory, Vol. 47, 1257-1261, 2001. [MLe]

  34. Contention Resolution with Constant Expected Delay, with L. A. Goldberg, P. D. MacKenzie, and M. S. Paterson. Journal of the ACM, Vol. 47, 1048-1096, 2000. [DaS, DiP, InW, RaC, ReS]

  35. Improved Bounds and Algorithms for Hypergraph 2-coloring, with J. Radhakrishnan, Random Structures & Algorithms, John Wiley and Sons, Vol. 16, 4-32, 2000. [GrC, RaC]

  36. Approximating Hyper-Rectangles: Learning and Pseudo-Random Sets, with P. Auer and P. M. Long, Journal of Computer and System Sciences, Vol. 57, 376-388, 1998. [MLe, RaC]

  37. Explicit OR-Dispersers with Polylogarithmic Degree, with M. Saks and S. Zhou, Journal of the ACM, Vol. 45, 123-154, 1998. [RaC]

  38. Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds, with A. Panconesi, SIAM Journal on Computing, Vol. 26, 350-368, 1997. (Winner of the Dijkstra Prize.) [DiP, GrC, RaC, ReS]

  39. The Local Nature of Δ-Coloring and its Algorithmic Applications, with A. Panconesi, Combinatorica, Vol. 15, 255-280, 1995. (A preliminary version was part of a paper that received a Best Student Paper Award at STOC 1992.) [DiP, GrC]

  40. Chernoff-Hoeffding Bounds for Applications with Limited Independence, with J. P. Schmidt and A. Siegel, SIAM Journal on Discrete Mathematics, Vol. 8, 223-250, 1995. [RaC, ReS]

Journal Publications

  1. Improved Guarantees for Offline Stochastic Matching via new Ordered Contention Resolution Schemes, with B. Brubach, N. Grammel, and W. Ma. Mathematics of Operations Research, accepted for publication. [DaS, EC, RaC, ReS]

  2. Stochastic Optimization and Learning for Two-Stage Supplier Problems, with B. Brubach, N. Grammel, D. G. Harris, L. Tsepenekas, and A. Vullikanti. ACM Transactions on Probabilistic Machine Learning, accepted for publication. [ApA, DaS, MLe, PHe, RaC, ReS, RoM]

  3. Assigning Tasks to Workers based on Historical Data: Online Task Assignment with Two-sided Arrivals, with J. P. Dickerson, K. A. Sankararaman, P. Xu, and Y. Xu. ACM Transactions on Economics and Computation, 12(2):6, 2024. [ApA, DaS, EC, RaC, ReS]

  4. Online Matching Frameworks under Stochastic Rewards, Product Ranking, and Unknown Patience, with B. Brubach, N. Grammel, and W. Ma. Operations Research, to appear. (Published online 27th October 2023.) [DaS, EC, RaC, ReS]

  5. Improved Sample-Complexity Bounds in Stochastic Optimization, with A. Baveja, A. Chavan, A. Nikiforov, and P. Xu. Operations Research, to appear. (Published online 17th October 2023.) [ApA, RaC]

  6. Flamingo: Environmental Impact Factor Matching for Life Cycle Assessment with Zero-Shot Machine Learning, with B. Balaji, G. Vunnava, N. Domingo, S. Gupta, H. Gupta, and G. Guest. ACM Journal on Computing and Sustainable Societies, Vol. 1, 1-23, 2023. [DaS, EC, MLe, SGr]

  7. Deploying Vaccine Distribution Sites for Improved Accessibility and Equity to Support Pandemic Response, with G. Li, A. Li, M. V. Marathe, L. Tsepenekas, and A. Vullikanti. Autonomous Agents and Multiagent Systems, 37(2):31, 2023. [ApA, DaS, Fai, MLe, PHe, ReS]

  8. Approximating weighted completion time via stronger negative correlation, with A. Baveja and X. Qu. Journal of Scheduling, 2023. (Published online on 30th March, 2023.) [ApA, RaC, ReS]

  9. Low-Complexity Scheduling Algorithms with Constant Queue Length and Throughput Guarantees, with S. S. Peruru, R. Ganti, and K. Jagannathan. Performance Evaluation, Vol. 157-158, 2022. [AdW, RaC, ReS]

  10. Dependent randomized rounding for clustering and partition systems with knapsack constraints, with D. G. Harris, T. Pensyl, and K. Trinh. Journal of Machine Learning Research (JMLR), 23(81), pages 1-41, 2022. Preliminary version in AISTATS 2020. [ApA, Fai, MLe, RaC, RoM]

  11. Allocation Problems in Ride Sharing Platforms: Online Matching with Offline Reusable Resources, with J. P. Dickerson, K. A. Sankararaman, and P. Xu. ACM Transactions on Economics and Computation, Vol. 9, No. 3, pages 13:1-13:17, 2021. [ApA, DaS, EC, KEx, PHe, RaC, ReS]

  12. Partial Resampling to Approximate Covering Integer Programs, with A. Chen and D. G. Harris. Random Structures & Algorithms, Vol. 58, pages 68-93, 2021. [ApA, RaC, RoM]

  13. Online Stochastic Matching: New Algorithms and Bounds, with B. Brubach, K. A. Sankararaman, and P. Xu. Algorithmica, Vol. 82, pages 2737-2783, 2020. [ApA, DaS, EC, RaC, ReS, RoM]

  14. Algorithms to Approximate Column-Sparse Packing Problems, with B. Brubach, K. A. Sankararaman, and P. Xu. ACM Transactions on Algorithms, Vol. 16, pages 10:1-10:32, 2020. [ApA, RaC, RoM]

  15. Attenuate Locally, Win Globally: Attenuation-based Frameworks for Online Stochastic Matching with Timeouts, with B. Brubach, K. A. Sankararaman, and P. Xu. Algorithmica, Vol. 82, pages 64-87, 2020. [ApA, DaS, EC, RaC, ReS, RoM]

  16. Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines, with N. Bansal and O. Svensson. Special issue of SIAM Journal on Computing for STOC 2016, published online October 2019. [ApA, RaC, ReS, RoM]

  17. Approximation Algorithms for Stochastic Clustering, with D. G. Harris, S. Li, T. Pensyl, and K. Trinh. Journal of Machine Learning Research (JMLR), Vol. 20, No. 153, pages 1-33, 2019. A preliminary version appeared in Proc. Conference on Neural Information Processing Systems (NeurIPS), pages 6041-6050, 2018. [ApA, DaS, Fai, MLe, RaC, RoM]

  18. The Moser-Tardos Framework with Partial Resampling, with D. G. Harris. Journal of the ACM, Vol. 66, pages 36:1-36:45, 2019. (This is a full version that combines our papers from STOC 2013 and FOCS 2013.) [ApA, InW, RaC, RoA, RoM]

  19. A Lottery Model for Center-type Problems with Outliers, with D. G. Harris, T. Pensyl, and K. Trinh. ACM Transactions on Algorithms, Vol. 15, Number 3, pages 36:1-36:25, 2019. [ApA, DaS, Fai, MLe, RaC, RoM]

  20. Improved Bounds in Stochastic Matching and Optimization, with A. Baveja, A. Chavan, A. Nikiforov, and P. Xu. Algorithmica, Vol. 80, Number 11, pages 3225-3252, 2018. [ApA, DaS, KEx, PHe, RaC, RoM]

  21. A Randomized Approximation Technique for Resource-Allocation Problems, with B. Saha. Random Structures & Algorithms, Vol. 52, pages 680-715, 2018. [ApA, RaC, ReS, RoM]

  22. Approximation Algorithms for Stochastic and Risk-Averse Optimization, with J. Byrka. SIAM Journal on Discrete Mathematics, Vol. 32, Issue 1, pages 44-63, 2018. [ApA, DaS, RaC, RoM]

  23. An Improved Approximation Algorithm for Knapsack Median Using Sparsification, with J. Byrka, T. Pensyl, B. Rybicki, J. Spoerhase, and K. Trinh. Algorithmica, Vol. 80, pages 1093-1114, 2018. (Published online 29 Jan., 2018.) [ApA, MLe, RaC, RoM]

  24. Improved Bounds and Algorithms for Graph Cuts and Network Reliability, with D. G. Harris. Random Structures & Algorithms, Vol. 52, Issue 1, pages 74-135, 2018. [ApA, RaC]

  25. A Constructive Lovász Local Lemma for Permutations, with D. G. Harris. Theory of Computing, Vol. 13, Article 17, pages 1-41, 2017. An earlier version appeared as "A Constructive Algorithm for the Lovász Local Lemma on Permutations" in the Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 907-925, 2014. [RaC]

  26. Algorithmic and enumerative aspects of the Moser-Tardos distribution, with D. G. Harris. ACM Transactions on Algorithms, Vol. 13, No. 3, pages 33:1-33:40, 2017. [RaC]

  27. An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization, with J. Byrka, T. Pensyl, B. Rybicki, and K. Trinh. ACM Transactions on Algorithms, Vol. 13, No. 2, pages 23:1-23:31, 2017. (Special issue of ACM TALG devoted to elected papers from SODA 2015.) [ApA, MLe, RaC, RoM]

  28. Efficient Computation of Balanced Structures, with D. G. Harris, E. Morsy, G. Pandurangan, and P. Robinson. Random Structures & Algorithms, Vol. 49, No. 2, pages 322-344, 2016. [DiP, RaC]

  29. On Computing Maximal Independent Sets of Hypergraphs in Parallel, with I. Bercea, N. Goyal, and D. G. Harris. ACM Transactions on Parallel Computing, Vol. 3, Issue 1, 2016. (Special Issue for selected papers from SPAA 2014.) [DiP, RaC]

  30. Distributed Algorithms for End-to-End Packet-Scheduling in Wireless Ad-Hoc Networks, with V. S. A. Kumar, M. V. Marathe, and S. Parthasarathy. ACM Transactions on Algorithms,Vol. 12, Issue 3, 2016. [AdW, DiP, RaC, ReS]

  31. A Note on Near-Optimal Coloring of Shift Hypergraphs, with D. G. Harris. Random Structures & Algorithms, Vol. 48, No. 1, pages 53-56, 2016. [GrC, RaC]

  32. Examining how marginalized stakeholders successfully redress their issues: a social networks approach, with S. Shivarajan and T. DuBois. Annals in Social Responsibility, Vol. 1, pages 108-130, 2015. [DaS, SGr, SoN]

  33. Lower Bounds on the Deterministic and Quantum Communication Complexity of Hamming-Distance Problems, with A. Ambainis, W. Gasarch and A. Utis. ACM Transactions on Computation Theory, Vol. 7, Issue 3, 2015.

  34. On the Energy Efficiency of Device Discovery in Mobile Opportunistic Networks: A Systematic Approach, with B. Han and J. Li. IEEE Transactions on Mobile Computing, Vol. 14, pages 786-799, 2015. [AdW, SGr, SoN]

  35. Your Friends Have More Friends Than You Do: Identifying Influential Mobile Users Through Random-Walk Sampling, with B. Han and J. Li. IEEE/ACM Transactions on Networking, Vol. 22, No. 5, pages 1389-1400, 2014. [AdW, PHe, RaC, SoN]

  36. On Random Sampling Auctions for Digital Goods, with S. Alaei and A. Malekian. ACM Transactions on Economics and Computation, Vol. 2, No. 3, 2014. [DaS, EC, RaC]

  37. Approximation Algorithms for Throughput Maximization in Wireless Networks with Delay Constraints, with V. S. A. Kumar, S. Parthasarathy, and G. Pei. IEEE/ACM Transactions on Networking, Vol. 21, 1988-2000, 2013. (Supplementary material.) [AdW, ApA, RaC]

  38. The Poor as Suppliers of Intellectual Property: A Social Network Approach to Sustainable Poverty Alleviation, with S. Shivarajan. Business Ethics Quarterly, Vol. 23, No. 3, 381-406, 2013. [SGr, SoN]

  39. Solving Packing Integer Programs via Randomized Rounding with Alterations, with N. Bansal, N. Korula, and V. Nagarajan. Theory of Computing, Vol. 8, 533-565, 2012. [ApA, DiP, RaC, RoM]

  40. The Effect of Random Edge Removal on Network Degree Sequence, with T. DuBois and S. Eubank. The Electronic Journal of Combinatorics, Vol. 19, P51, 2012. [DaS, RaC, SoN]

  41. Mobile Data Offloading through Opportunistic Communications and Social Participation, with B. Han, P. Hui, V. S. A. Kumar, M. V. Marathe, and J. Shao. IEEE Transactions on Mobile Computing, Volume 11(5), 821-834, 2012. (Published earlier online.) [AdW, RaC, SoN]

  42. New Constructive Aspects of the Lovász Local Lemma, with B. Haeupler and B. Saha. Journal of the ACM, Volume 58, Issue 6, 2011. [ApA, GrC, RaC]

  43. Capacity of Wireless Networks under SINR Interference Constraints, with D. Chafekar, V. S. A. Kumar, M. V. Marathe, and S. Parthasarathy. Springer-Verlag Wireless Networks, Vol. 17(7), 1605-1624, 2011. [AdW, ApA]

  44. Maximum Bipartite Flow in Networks with Adaptive Channel Width, with Y. Azar, A. Mądry, T. Moscibroda and D. Panigrahi. Theoretical Computer Science, Vol. 412, 2577-2587, 2011. Special issue dedicated to selected papers from ICALP 2009. [AdW, ApA, RaC, RoM]

  45. A Unified Approach to Scheduling on Unrelated Parallel Machines, with V. S. A. Kumar, M. V. Marathe, and S. Parthasarathy. Journal of the ACM, Vol. 56, 2009. [ApA, Fai, RaC, ReS, RoM]

  46. Scheduling on Unrelated Machines under Tree-Like Precedence Constraints, with V. S. A. Kumar, M. V. Marathe, and S. Parthasarathy. Algorithmica, Vol. 55, 205-226, 2009. (Special issue of Algorithmica dedicated to selected papers from APPROX 2005. Published online first; SpringerLink Date: Sept. 15, 2007.) [ApA, RaC, ReS, RoM]

  47. A Note on the Distribution of the Number of Prime Factors of the Integers. Information Processing Letters, Vol. 109, Issue 2, 133-135, 2008. [RaC]

  48. Efficient and Resilient Backbones for Multihop Wireless Networks, with S. Lee, B. Bhattacharjee, and S. Khuller. IEEE Transactions on Mobile Computing, Vol. 7, 1349-1362, 2008. [AdW, DiP, RaC]

  49. Cost-Sharing Mechanisms for Network Design, with A. Gupta and É. Tardos. Algorithmica, Vol. 50, 98-119, 2008. [ApA, EC, RaC]

  50. Integrality Ratio for Group Steiner Trees and Directed Steiner Trees, with E. Halperin, G. Kortsarz, R. Krauthgamer, and N. Wang. SIAM Journal on Computing, Vol. 36, 1494-1511, 2007. [ApA, RaC, RoM]

  51. Efficient Lookup on Unstructured Topologies, with R. Morselli, B. Bhattacharjee, and M. Marsh. IEEE Journal on Selected Areas in Communications (Special Issue on Peer-to-Peer Communications and Applications), Vol. 25, pages 62-72, 2007. Full version with proofs (Technical Report CS-TR-4772, Department of Computer Science, University of Maryland, December 2005) [DiP, InW, RaC]

  52. An Extension of the Lovász Local Lemma, and its Applications to Integer Programming. SIAM Journal on Computing, Vol. 36, 609-634, 2006. [ApA, GrC, RaC, RoA, RoM]

  53. Dependent Rounding and its Applications to Approximation Algorithms, with R. Gandhi, S. Khuller, and S. Parthasarathy. Journal of the ACM, Vol. 53, 324-360, 2006. [ApA, RaC, RoM]

  54. Provable Algorithms for Parallel Generalized Sweep Scheduling, with V. S. A. Kumar, M. V. Marathe, S. Parthasarathy, and S. Zust. Journal of Parallel and Distributed Computing, Vol. 16, 807-821, 2006. [ApA, DiP, RaC, ReS]

  55. Resilient Multicast using Overlays, with S. Banerjee, S. Lee, and B. Bhattacharjee. IEEE/ACM Transactions on Networking, Vol. 14, 237-248, 2006. [DiP, InW, RaC]

  56. Approximation Algorithms for Channel Allocation Problems in Broadcast Networks, with R. Gandhi, S. Khuller, and N. Wang. Networks, Vol. 47, 225-236, 2006. [ApA, DiP, RaC]

  57. An Improved Approximation Ratio for the Covering Steiner Problem, with A. Gupta. Theory of Computing, Vol. 2, 53-64, 2006. [ApA, RaC, RoM]

  58. An Improved Approximation Algorithm For Vertex Cover with Hard Capacities, with R. Gandhi, E. Halperin, S. Khuller, and G. Kortsarz. Journal of Computer and System Sciences, Vol. 72, 16-33, 2006. [ApA, RaC, RoM]

  59. P5: A Protocol for Scalable Anonymous Communication, with R. Sherwood and B. Bhattacharjee. Journal of Computer Security, Vol. 13, 839-876, 2005. [InW, RaC]

  60. Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons, with D. Dubhashi, A. Mei, A. Panconesi, and J. Radhakrishnan. Journal of Computer and System Sciences, Vol. 71, 467-479, 2005. [AdW, DiP, RaC]

  61. Modelling Disease Outbreaks in Realistic Urban Social Networks, with S. Eubank, H. Guclu, V. S. A. Kumar, M. V. Marathe, Z. Toroczkai, and N. Wang. Nature, Vol. 429, 180-184, May 2004. (Supplemental Information) The same version is also available at Nature's website - subscription required. [DaS, PHe, RaC, SoN]

  62. Finding Large Independent Sets in Graphs and Hypergraphs, with H. Shachnai. SIAM Journal on Discrete Mathematics, Vol. 18, 488-500, 2004. [DiP, RaC]

  63. Approximation Algorithms for Partial Covering Problems, with R. Gandhi and S. Khuller. Journal of Algorithms, Vol. 53, 55-84, 2004. [ApA, RaC, RoM]

  64. On the Approximability of Clique and Related Maximization Problems. Journal of Computer and System Sciences, Vol. 67, 633-651, 2003. [ApA, RaC]

  65. When does a Random Robin Hood win?, with W. Gasarch and E. Golub. Theoretical Computer Science, Vol. 304, Issues 1-3, 477-484, 2003. [RaC]

  66. Statistical Analysis of Algorithms: A Case Study of Market-Clearing Mechanisms in the Power Industry, with C. Barrett, D. Cook, V. Faber, G. Hicks, A. Marathe, M. V. Marathe, Y. J. Sussmann, and H. Thornquist. Journal of Graph Algorithms and Applications, Vol. 7, 3-31, 2003.

  67. Wavelength Rerouting in Optical Networks, or the Venetian Routing Problem, with A. Caprara, G. Italiano, G. Mohan, and A. Panconesi. Journal of Algorithms, Vol. 45, 93-125, 2002. [ApA, InW]

  68. Approximating the Domatic Number, with U. Feige, M. M. Halldorsson, and G. Kortsarz. SIAM Journal on Computing, Vol. 32, 172-195, 2002. [ApA, RaC]

  69. Approximation Algorithms for the Covering Steiner Problem, with G. Konjevod and R. Ravi. Random Structures & Algorithms (Special Issue on Probabilistic Methods in Combinatorial Optimization), John Wiley and Sons, Vol. 20, 465-482, 2002. [ApA, RaC, RoM]

  70. New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning, with F. T. Leighton, C.-J. Lu and S. B. Rao. SIAM Journal on Computing, Vol. 31, 626-641, 2001. [ApA, InW, RaC, RoA, RoM]

  71. Improved Bounds on the Sample Complexity of Learning, with Y. Li and P. M. Long. Journal of Computer and System Sciences, Vol. 62, 516-527, 2001. [MLe]

  72. A Constant-Factor Approximation Algorithm for Packet Routing and Balancing Local vs. Global Criteria, with C. P. Teo. SIAM Journal on Computing, Vol. 30, 2051-2068, 2001. [ApA, InW, RoA, RoM]

  73. The One-Inclusion Graph Algorithm is Near-Optimal for the Prediction Model of Learning, with Y. Li and P. M. Long. IEEE Transactions on Information Theory, Vol. 47, 1257-1261, 2001. [MLe]

  74. Better Approximation Guarantees for Job-Shop Scheduling, with L. A. Goldberg, M. S. Paterson and E. Sweedyk. SIAM Journal on Discrete Mathematics, Vol. 14, 67-92, 2001. [ApA, RaC, ReS]

  75. Contention Resolution with Constant Expected Delay, with L. A. Goldberg, P. D. MacKenzie, and M. S. Paterson. Journal of the ACM, Vol. 47, 1048-1096, 2000. [DaS, DiP, InW, RaC, ReS]

  76. Improved Algorithms via Approximations of Probability Distributions, with S. Chari and P. Rohatgi. Journal of Computer and System Sciences, Vol. 61, 81-107, 2000. [DiP, RaC]

  77. Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems, with A. Baveja. Mathematics of Operations Research, Vol. 25, 255-280, 2000. [ApA, InW, RaC, ReS, RoA, RoM]

  78. Retrieval Scheduling For Collaborative Multimedia Presentations, with Ping Bai and B. Prabhakaran. ACM/Springer-Verlag Multimedia Systems Journal, Vol. 8, 146-155, 2000. [InW, ReS]

  79. Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families, with M. Saks, S. Zhou, and D. Zuckerman, Information Processing Letters, Vol. 73, 29-32, 2000. [InW, RaC]

  80. Improved Bounds and Algorithms for Hypergraph 2-coloring, with J. Radhakrishnan, Random Structures & Algorithms, John Wiley and Sons, Vol. 16, 4-32, 2000. [GrC, RaC]

  81. Approximating Low-Congestion Routing and Column-Restricted Packing Problems, with A. Baveja, Information Processing Letters, Vol. 74, 19-25, 2000. [ApA, InW, RaC, RoA, RoM]

  82. Improved Approximation Guarantees for Packing and Covering Integer Programs, SIAM Journal on Computing, Vol. 29, 648-670, 1999. [ApA, RaC, RoM]

  83. Computing with Very Weak Random Sources, with D. Zuckerman, SIAM Journal on Computing, Vol. 28, 1433-1459, 1999. [RaC]

  84. Explicit OR-Dispersers with Polylogarithmic Degree, with M. Saks, and S. Zhou, Journal of the ACM, Vol. 45, 123-154, 1998. [RaC]

  85. Approximating Hyper-Rectangles: Learning and Pseudo-Random Sets, with P. Auer and P. M. Long, Journal of Computer and System Sciences, Vol. 57, 376-388, 1998. [MLe, RaC]

  86. Improved Parallel Approximation of a Class of Integer Programming Problems, with N. Alon, Algorithmica, Vol. 17, 449-462, 1997. [DiP, RaC, RoM]

  87. Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds, with A. Panconesi, SIAM Journal on Computing, Vol. 26, 350-368, 1997. [DiP, GrC, RaC, ReS]

  88. On the Complexity of Distributed Network Decomposition, with A. Panconesi, Journal of Algorithms, Vol. 20, 356-374, 1996. [DiP, ReS]

  89. Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems, with S. Chari and P. Rohatgi. SIAM Journal on Computing, Vol. 24, 1036-1050, 1995. [DiP, RaC]

  90. Chernoff-Hoeffding Bounds for Applications with Limited Independence, with J. P. Schmidt and A. Siegel, SIAM Journal on Discrete Mathematics, Vol. 8, 223-250, 1995. [RaC, ReS]

  91. The Local Nature of Δ-Coloring and its Algorithmic Applications, with A. Panconesi, Combinatorica, Vol. 15, 255-280, 1995. [DiP, GrC]

  92. On Finding the Minimum Bandwidth of Interval Graphs, with R. Mahesh and C. P. Rangan, Information and Computation, Vol. 95, 218-224, 1991.

  93. Efficient Algorithms for the Minimum Weighted Dominating Clique Problem on Permutation Graphs, with C. P. Rangan, Theoretical Computer Science, Vol. 91, 1-21, 1991.

Refereed Conference Publications

  1. Concentration of Submodular Functions and Read-k Families Under Negative Dependence, with S. Duppala, G. Li, J. Luque, and R. Valieva. To appear, Proc. Annual Symposium on Innovations in Theoretical Computer Science (ITCS), 2025. [Fai, RaC, ReS, RoM]

  2. Online Dependent Rounding Schemes for Bipartite Matchings, with Applications, with J. (Seffi) Naor and D. Wajc. To appear, Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025. (A mostly up-to-date version with a previous title.) [DaS, EC, Fai, PHe, RaC, ReS, RoM]

  3. Parakeet: Emission Factor Recommendation for Life Cycle Assessments with Generative AI, with B. Balaji, F. Meymand, G. Vunnava, N. Domingo, A. Faridee, S. Ramalingam, S. Gupta, A. Wang, H. Gupta, K. Axten, J. Hakian, Q. Tu, and J. Kramer. To appear, Workshop on Tackling Climate Change with Machine Learning, Annual Conference on Neural Information Processing Systems (NeurIPS), 2024. [DaS, EC, MLe, SGr]

  4. Promoting External and Internal Equities under Ex-Ante/Ex-Post Metrics in Online Resource Allocation, with K. A. Sankararaman and P. Xu. Proc. International Conference on Machine Learning (ICML), 2024. (Spotlight Paper.) [DaS, Fai, PHe, RaC, ReS]

  5. Barter Exchange with Shared Item Valuations, with J. Luque, S. Duppala, and J. P. Dickerson. Proc. The Web Conference (formerly known as WWW, the International World Wide Web Conference), 199-210, 2024. [ApA, DaS, EC, Fai, InW, KEx, RaC, ReS, RoM]

  6. Planning to Fairly Allocate: Probabilistic Fairness in the Restless Bandit Setting, with C. Herlihy, A. Prins, and J. P. Dickerson. Proc. ACM Conference on Knowledge Discovery and Data Mining (KDD), 732-740, 2023. (A preliminary version appeared in the Workshop on Responsible Decision Making in Dynamic Environments at the International Conference on Machine Learning (ICML), 2022.) [DaS, Fai, MLe, PHe, RaC]

  7. Scaling Carbon Footprinting: Challenges and Opportunities, with B. Balaji, G. Guest, G. Vunnava, J. Kramer, and M. Taptich. Proc. ACM SIGCAS/SIGCHI Conference on Computing and Sustainable Societies (COMPASS), 2023. (Poster track.) Also presented at the AAAI 2023 Fall Symposium on Artifical Intelligence and Climate: The Role of AI in a Climate-Smart Sustainable Future, 2023. [DaS, EC, MLe, SGr]

  8. Group Fairness in Set Packing Problems, with S. Duppala, J. Luque, and J. P. Dickerson. Proc. International Joint Conference on Artificial Intelligence (IJCAI), 391-399, 2023. Also accepted to the First Workshop on Computational Fair Division (CFD), co-located with IJCAI 2023. [DaS, Fai, KEx, RaC]

  9. Efficient and Equitable Deployment of Mobile Vaccine Distribution Centers, with D. Q. Chen, A. Li, G. Li, M. V. Marathe, L. Tsepenekas, and A. Vullikanti. Proc. International Joint Conference on Artificial Intelligence (IJCAI), 64-72, 2023. [ApA, DaS, Fai, MLe, PHe, ReS]

  10. Rawlsian Fairness in Online Bipartite Matching: Two-sided, Group, and Individual, with S. A. Esmaeili, S. Duppala, D. Cheng, V. Nanda, and J. P. Dickerson. Proc. Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI), 5624-5632, 2023. (A preliminary version with fewer results that was co-authored with Esmaeili, Duppala, Nanda, and Dickerson, appeared as a refereed two-page abstract at AAMAS 2022.) [DaS, Fai, EC, RaC, ReS]

  11. Improved Bi-Point Rounding Algorithms and a Golden Barrier for k-median, with K. Gowda, T. Pensyl, and K. Trinh. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 987-1011, 2023. [ApA, MLe, RaC, RoM]

  12. Effective Social Network-Based Allocation of COVID-19 Vaccines, with J. Chen, S. Hoops, A. Marathe, H. Mortveit, B. Lewis, S. Venkatramanan, A. Haddadan, P. Bhattacharya, A. Adiga, A. Vullikanti, M. L. Wilson, G. Ehrlich, M. Fenster, S. Eubank, C. Barrett, and M. Marathe. ACM Conference on Knowledge Discovery and Data Mining (KDD), pages 4675-4683, 2022. [DaS, PHe, ReS, SoN]

  13. Forecasting Patient Outcomes in Kidney Exchange, with N. Durvasula and J. P. Dickerson. (A fuller version is also available.) Proc. International Joint Conference on Artificial Intelligence (IJCAI-ECAI), pages 5052-5058, 2022. (AI for Good track.) [DaS, KEx, PHe]

  14. Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks, with A. Babay, M. Dinitz, L. Tsepenekas, and A. Vullikanti. Proc. International Conference on Artifical Intelligence and Statistics (AISTATS), pages 11641-11654, 2022. [ApA, DaS, MLe, PHe, RaC, ReS]

  15. A New Notion of Individually Fair Clustering: alpha-Equitable k-Center, with D. Chakrabarti, J. P. Dickerson, S. A. Esmaeili, and L. Tsepenekas. Proc. International Conference on Artifical Intelligence and Statistics (AISTATS), pages 6387-6408, 2022. [ApA, DaS, Fai, MLe, RaC]

  16. Fair Disaster Containment via Graph-Cut Problems, with M. Dinitz, L. Tsepenekas, and A. Vullikanti. Proc. International Conference on Artifical Intelligence and Statistics (AISTATS), pages 6321-6333, 2022. [ApA, DaS, Fai, PHe, RaC, ReS]

  17. Deploying Vaccine Distribution Sites for Improved Accessibility and Equity to Support Pandemic Response, with G. Li, A. Li, M. V. Marathe, L. Tsepenekas, and A. Vullikanti. Proc. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 789-797, 2022. (Best Student Paper Award.) [ApA, DaS, Fai, MLe, PHe, ReS]

  18. The Generalized Magician Problem under Unknown Distributions and Related Applications, with P. Xu. Proc. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1219-1227, 2022. [DaS, Fai, EC, RaC, ReS]

  19. Theoretical Models and Preliminary Results for Contact Tracing and Isolation, with G. Li, A. Haddadan, A. Li, M. V. Marathe, A. Vullikanti, and Z. Zhao. Appears as a refereed two-page extended abstract, Proc. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1672-1674, 2022. [ApA, DaS, MLe, PHe, ReS]

  20. Rawlsian Fairness in Online Bipartite Matching: Two-sided, Group, and Individual, with S. A. Esmaeili, S. Duppala, V. Nanda, and J. P. Dickerson. The version here is a longer form of the refereed two-page extended abstract that appears in the Proc. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1583-1585, 2022. [DaS, Fai, EC, RaC, ReS]

  21. Improved Guarantees for Offline Stochastic Matching via new Ordered Contention Resolution Schemes, with B. Brubach, N. Grammel, and W. Ma. Proc. Conference on Neural Information Processing Systems (NeurIPS), pages 27184-27195, 2021. [DaS, EC, RaC, ReS]

  22. Fair Clustering Under a Bounded Cost, with S. A. Esmaeili, B. Brubach, and J. P. Dickerson. Proc. Conference on Neural Information Processing Systems (NeurIPS), pages 14345-14357, 2021. [ApA, DaS, Fai, MLe, RaC, RoM]

  23. Property B: Two-coloring Non-uniform Hypergraphs, with J. Radhakrishnan. Proc. Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST & TCS), pages 31:1-31:8, 2021. [GrC, RaC]

  24. Approximating Two-Stage Stochastic Supplier Problems, with B. Brubach, N. Grammel, D. G. Harris, L. Tsepenekas, and A. Vullikanti. Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 23:1-23:22, 2021. [ApA, DaS, MLe, PHe, RaC, ReS, RoM]

  25. A Bayesian Optimization Approach to Estimating Expected Match Time and Organ Quality in Kidney Exchange, with N. Durvasula and J. P. Dickerson. Appeared as a full-length contributed talk, Proc. ICLR Workshop on AI for Public Health, 2021. [DaS, KEx, PHe]

  26. Follow Your Star: New Frameworks for Online Stochastic Matching with Known and Unknown Patience, with B. Brubach, N. Grammel, and W. Ma. Proc. International Conference on Artifical Intelligence and Statistics (AISTATS), pages 2872-2880, 2021. [DaS, EC, RaC, ReS]

  27. Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints, with B. Brubach, D. Chakrabarti, J. P. Dickerson, and L. Tsepenekas. Proc. Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI), pages 6822-6830, 2021. [ApA, Bio, DaS, Fai, MLe, PHe, RaC, ReS]

  28. A Pairwise Fair and Community-preserving Approach to k-center clustering, with B. Brubach, D. Chakrabarti, J. P. Dickerson, S. Khuller, and L. Tsepenekas. Proc. International Conference on Machine Learning (ICML), pages 1178-1189, 2020. [ApA, DaS, Fai, MLe, RaC, ReS]

  29. Meddling Metrics: the Effects of Measuring and Constraining Partisan Gerrymandering on Voter Incentives, with B. Brubach and S. Zhao. [DaS, Fai, ReS]

  30. Dependent randomized rounding for clustering and partition systems with knapsack constraints, with D. G. Harris, T. Pensyl, and K. Trinh. Proc. International Conference on Artifical Intelligence and Statistics (AISTATS), pages 2273-2283, 2020. [ApA, Fai, MLe, RaC, RoM]

  31. Balancing the Tradeoff between Profit and Fairness in Rideshare Platforms during High-Demand Hours, with V. Nanda, P. Xu. J. P. Dickerson, and K. A. Sankararaman. [ApA, DaS, EC, Fai, RaC, ReS]

  32. Mix and Match: Markov Chains and Mixing Times for Matching in Rideshare, with M. J. Curry, J. P. Dickerson, K. A. Sankararaman, Y. Wan, and P. Xu. Proc. Fifteenth Conference on Web and Internet Economics (WINE), pages 129-141, 2019. [DaS, EC, RaC, ReS]

  33. Online Resource Allocation with Matching Constraints, with J. P. Dickerson, K. A. Sankararaman, K. Sarpatwar, K-L. Wu, and P. Xu. Proc. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1681-1689, 2019. [ApA, DaS, EC, Fai, RaC, ReS, RoM]

  34. Balancing Relevance and Diversity in Online Bipartite Matching via Submodularity, with J. P. Dickerson, K. A. Sankararaman, and P. Xu. Proc. Thirty-Third AAAI Conference on Artificial Intelligence (AAAI), pages 1877-1884, 2019. [ApA, DaS, EC, Fai, RaC, ReS]

  35. A Unified Approach to Online Matching with Conflict-Aware Constraints, with P. Xu, Y. Shi, H. Cheng, J. P. Dickerson, K. A. Sankararaman, Y. Tong, and L. Tsepenekas. Proc. Thirty-Third AAAI Conference on Artificial Intelligence (AAAI), pages 2221-2228, 2019. [ApA, DaS, EC, RaC, ReS]

  36. Approximation Algorithms for Stochastic Clustering, with D. G. Harris, S. Li, T. Pensyl, and K. Trinh. Proc. Conference on Neural Information Processing Systems (NeurIPS), pages 6041-6050, 2018. [ApA, DaS, Fai, MLe, RaC, RoM]

  37. Assigning Tasks to Workers based on Historical Data: Online Task Assignment with Two-sided Arrivals, with J. P. Dickerson, K. A. Sankararaman, and P. Xu. Proc. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 318-326, 2018. [ApA, DaS, EC, RaC, ReS]

  38. Hierarchical Scheduling Algorithms with Throughput Guarantees and Low Delay, with P. S. Swamy, R. Ganti, and K. Jagannathan. Proc. International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), pages 1-8, 2018. [AdW, RaC, ReS]

  39. Allocation Problems in Ride Sharing Platforms: Online Matching with Offline Reusable Resources, with J. P. Dickerson, K. A. Sankararaman, and P. Xu. Proc. Thirty-Second AAAI Conference on Artificial Intelligence (AAAI), 2018. [ApA, DaS, EC, KEx, PHe, RaC, ReS]

  40. Algorithms to Approximate Column-Sparse Packing Problems, with B. Brubach, K. A. Sankararaman, and P. Xu. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 311-330, 2018. [ApA, RaC, RoM]

  41. Better Greedy Sequence Clustering with Fast Banded Alignment, with B. Brubach, J. Ghurye, and M. Pop. Proc. Annual Workshop on Algorithms in Bioinformatics (WABI), pages 3:1-3:13, 2017. [Bio, MLe]

  42. A Lottery Model for Center-type Problems with Outliers, with D. G. Harris, T. Pensyl, and K. Trinh. Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 10:1-10:19, 2017. [ApA, DaS, Fai, MLe, RaC, RoM]

  43. Attenuate Locally, Win Globally: Attenuation-based Frameworks for Online Stochastic Matching with Timeouts, with B. Brubach, K. A. Sankararaman, and P. Xu. Proc. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1223-1231, 2017. [ApA, DaS, EC, RaC, ReS, RoM]

  44. Online Assignment Problems in Crowdsourcing Markets: Theory and Practice, with P. Xu, K. Sarpatwar, and K-L. Wu. Refereed paper; appears as an extended abstract in the Proc. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1763-1765, 2017. [ApA, DaS, EC, RaC, ReS, RoM]

  45. New Algorithms, Better Bounds, and a Novel Model for Online Stochastic Matching, with B. Brubach, K. A. Sankararaman, and P. Xu. Proc. European Symposium on Algorithms (ESA), pages 24:1-24:16, 2016. [ApA, DaS, EC, RaC, ReS, RoM]

  46. Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines, with N. Bansal and O. Svensson. Proc. ACM Symposium on Theory of Computing (STOC), pages 156-167, 2016. (Invited to the special issue of SIAM Journal on Computing for STOC 2016.) [ApA, RaC, ReS, RoM]

  47. Partial Resampling to Approximate Covering Integer Programs, with A. Chen and D. G. Harris. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1984-2003, 2016. (The link here is to an extended version.) [ApA, RaC, RoM]

  48. Algorithmic and enumerative aspects of the Moser-Tardos distribution, with D. G. Harris. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2004-2023, 2016. (The link here is to an extended version.) [RaC]

  49. An Improved Approximation Algorithm for Knapsack Median Using Sparsification, with J. Byrka, T. Pensyl, B. Rybicki, J. Spoerhase, and K. Trinh. Proc. European Symposium on Algorithms (ESA), pages 275-287, 2015. (The link here is to an extended version.) [ApA, MLe, RaC, RoM]

  50. Improved Bounds in Stochastic Matching and Optimization, with A. Baveja, A. Chavan, A. Nikiforov, and P. Xu. Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 124-134, 2015. [ApA, DaS, KEx, PHe, RaC, RoM]

  51. Selling Tomorrow's Bargains Today, with M. Abolhassani, H. Esfandiari, M. T. Hajiaghayi, H. Mahini, and D. Malec. Proc. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 337-345, 2015. [ApA, DaS, EC, RaC]

  52. An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization, with J. Byrka, T. Pensyl, B. Rybicki, and K. Trinh. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 737-756, 2015. (The link here is to an extended version that corrects an error in the SODA version. This paper will appear in the special issue of ACM TALG devoted to selected papers from SODA 2015.) [ApA, MLe, RaC, RoM]

  53. 'Beating the news' with EMBERS: Forecasting Civil Unrest using Open Source Indicators, with N. Ramakrishnan et al. Proc. ACM Conference on Knowledge Discovery and Data Mining (KDD), pages 1799-1808, 2014. [DaS, MLe, PHe, SoN]

  54. On Computing Maximal Independent Sets of Hypergraphs in Parallel, with I. Bercea, N. Goyal, and D. G. Harris. Proc. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 42-50, 2014. [DiP, RaC]

  55. A Constructive Algorithm for the Lovász Local Lemma on Permutations, with D. G. Harris. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 907-925, 2014. (This is a full version of the paper.) [RaC]

  56. Improved Bounds and Algorithms for Graph Cuts and Network Reliability, with D. G. Harris. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 259-278, 2014. (The results of the conference version are correct, but there was an error in the analysis. This is an extended version that fixes these errors.) [ApA, RaC]

  57. The Moser-Tardos Framework with Partial Resampling, with D. G. Harris. Proc. IEEE Symposium on Foundations of Computer Science (FOCS), pages 469-478, 2013. (This is a full version that combines this FOCS 2013 paper with our STOC 2013 paper.) [ApA, InW, RaC, RoA, RoM]

  58. Efficient Computation of Balanced Structures, with D. G. Harris, E. Morsy, G. Pandurangan, and P. Robinson. Proc. International Colloquium on Automata, Languages, and Programming (ICALP), pages 581-593, 2013. (This version is more detailed than the one in the ICALP proceedings.) [DiP, RaC]

  59. Constraint Satisfaction, Packet Routing, and the Lovász Local Lemma, with D. G. Harris. Proc. ACM Symposium on Theory of Computing (STOC), pages 685-694, 2013. (This version is more detailed than the one in the STOC proceedings.) [ApA, InW, RaC, RoA]

  60. Enabling Energy-Aware Collaborative Mobile Data Offloading for Smartphones, with A. Y. Ding, B. Han, Y. Xiao, P. Hui, M. Kojo, and S. Tarkoma. Proc. IEEE International Conference on Sensing, Communication, and Networking (SECON), 2013. [AdW, SGr, SoN]

  61. eDiscovery: Energy Efficient Device Discovery for Mobile Opportunistic Communications, with B. Han. Proc. IEEE International Conference on Network Protocols (ICNP), pages 1-10, 2012. [AdW, SGr, SoN]

  62. Examining the Evolution of Ties in Social Networks: A Longitudinal Multi-Method Study, with S. Shivarajan and T. DuBois. Proc. Academy of Management Annual Meeting, 2012. (Adjudged one of the best accepted papers; appears in the Best Paper Proceedings.) [DaS, SGr, SoN]

  63. The Poor as Suppliers of Intellectual Property: A Social Networks Approach to Poverty Alleviation, with S. Shivarajan. Proc. Academy of Management Annual Meeting, 2012. [SGr, SoN]

  64. Your Friends Have More Friends Than You Do: Identifying Influential Mobile Users Through Random Walks, with B. Han. Proc. ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pages 5-14, 2012. [AdW, PHe, RaC, SoN]

  65. Optimizing Epidemic Protection for Socially Essential Workers, with C. Barrett, R. Beckman, K. Bisset, J. Chen, T. DuBois, S. Eubank, V. S. A. Kumar, B. Lewis, M. V. Marathe, and P. Stretz. Proc. ACM International Health Informatics Symposium (IHI), pages 31-40, 2012. [DaS, PHe, RaC, SoN]

  66. Networking Lessons: From Computers to Water, with I. Narayanan, A. Vasan, V. Sarangan, and A. Sivasubramaniam. Proc. Workshop on Energy in Communication, Information, and Cyber-Physical Systems (E6), 2012. (Part of the Fourth International Conference on Communication Systems and Networks (COMSNETS), 2012.) [InW, ReS, SGr]

  67. Predicting Trust and Distrust in Social Networks, with T. DuBois and J. Golbeck. Proc. IEEE International Conference on Social Computing, pages 418-424, 2011. (Best Paper Award.) [DaS, InW, MLe, RaC, SoN]

  68. Approximation Algorithms for Throughput Maximization in Wireless Networks with Delay Constraints, with V. S. A. Kumar, S. Parthasarathy, and G. Pei. Proc. IEEE Conference on Computer Communications (INFOCOM), pages 1116-1124, 2011. [AdW, ApA, RaC]

  69. New Constructive Aspects of the Lovász Local Lemma, with B. Haeupler and B. Saha. Proc. IEEE Symposium on Foundations of Computer Science (FOCS), pages 397-406, 2010. [ApA, GrC, RaC]

  70. Cellular Traffic Offloading Through Opportunistic Communications: A Case Study, with B. Han, P. Hui, V. S. A. Kumar, M. V. Marathe, and G. Pei. Proc. ACM MobiCom Workshop on Challenged Networks (CHANTS), pages 31-38, 2010. [AdW, RaC]

  71. Fault-Tolerant Facility Location: a Randomized Dependent LP-rounding Algorithm, with J. Byrka and C. Swamy. Proc. MPS Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 244-257, 2010. [ApA, RaC, RoM]

  72. On k-Column Sparse Packing Programs, with N. Bansal, N. Korula, and V. Nagarajan. Proc. MPS Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 369-382, 2010. [ApA, RaC, RoM]

  73. A New Approximation Technique for Resource-Allocation Problems, with B. Saha. Proc. First Annual Symposium on Innovations in Computer Science (ICS), pages 342-357, 2010. (ICS, renamed ITCS (Innovations in Theoretical Computer Science) in 2011, is an exciting forum started in 2010, aiming to be a high-quality conference in theoretical computer science.) [ApA, RaC, ReS, RoM]

  74. Improving Recommendation Accuracy by Clustering Social Networks with Trust, with T. DuBois, J. Golbeck, and J. Kleint. Proc. ACM RecSys'09 Workshop on Recommender Systems and the Social Web, 2009. (Eight pages.) [DaS, InW, RaC, SoN]

  75. Rigorous Probabilistic Trust-inference with Applications to Clustering, with T. DuBois and J. Golbeck. Proc. IEEE/WIC/ACM International Conference on Web Intelligence (WI), pages 655-658, 2009. [DaS, InW, RaC, SoN]

  76. On Random Sampling Auctions for Digital Goods, with S. Alaei and A. Malekian. Proc. ACM Conference on Electronic Commerce (EC), pages 187-196, 2009. [DaS, EC, RaC]

  77. Maximum Bipartite Flow in Networks with Adaptive Channel Width, with Y. Azar, A. Mądry, T. Moscibroda and D. Panigrahi. Proc. International Colloquium on Automata, Languages, and Programming (ICALP), pages 351-362, 2009. [AdW, ApA, RaC, RoM]

  78. Distributed Strategies for Channel Allocation and Scheduling in Software-Defined Radio Networks, with B. Han, V. S. A. Kumar, M. V. Marathe, and S. Parthasarathy. Proc. IEEE Conference on Computer Communications (INFOCOM), pages 1521-1529, 2009. [AdW, DiP, RaC, ReS]

  79. Budgeted Allocations in the Full-Information Setting. Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 247-253, 2008. [ApA, EC, RoM]

  80. The Randomized Coloring Procedure with Symmetry-Breaking, with S. Pemmaraju. Proc. International Colloquium on Automata, Languages, and Programming (ICALP), pages 306-319, 2008. [GrC, RaC]

  81. Capacity of Asynchronous Random-Access Scheduling in Wireless Networks, with D. Chafekar, V. S. A. Kumar, D. Levin, M. V. Marathe, and S. Parthasarathy. Proc. IEEE Conference on Computer Communications (INFOCOM), pages 1148-1156, 2008. [AdW, ApA, DiP, RaC]

  82. Approximation Algorithms for Computing Capacity of Wireless Networks with SINR constraints, with D. Chafekar, V. S. A. Kumar, M. V. Marathe, and S. Parthasarathy. Proc. IEEE Conference on Computer Communications (INFOCOM), pages 1166-1174, 2008. [AdW, ApA]

  83. Improved Algorithmic Versions of the Lovász Local Lemma. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 611-620, 2008. [GrC, RaC]

  84. Distributed Ranked Search, with V. Gopalakrishnan, R. Morselli, B. Bhattacharjee, and P. Keleher. Proc. Annual International Conference on High Performance Computing (HiPC), pages 7-20, 2007. (Best Paper Award.) [DiP, InW, RaC]

  85. Cross-Layer Latency Minimization in Wireless Networks with SINR Constraints, with D. Chafekar, V. S. A. Kumar, M. V. Marathe, and S. Parthasarathy. Proc. ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pages 110-119, 2007. [AdW, ApA, RaC, RoA]

  86. Provable Algorithms for Joint Optimization of Transport, Routing and MAC layers in Wireless Ad Hoc Networks, with V. S. A. Kumar, M. V. Marathe, and S. Parthasarathy. Proc. DialM-POMC Workshop on Foundations of Mobile Computing, 2007. (Invited and refereed paper; eight pages.) [AdW, ApA]

  87. Approximation Algorithms for Stochastic and Risk-Averse Optimization. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1305-1313, 2007. [ApA, RaC, RoM]

  88. Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems, with A. Ambainis, W. Gasarch and A. Utis. Proc. International Symposium on Algorithms and Computation (ISAAC), pages 628-637, 2006. [Earlier version with all proofs]

  89. A Client-Driven Approach for Channel Management in Wireless LANs, with A. Mishra, V. Brik, S. Banerjee, and W. Arbaugh. Proc. IEEE Conference on Computer Communications (INFOCOM), 2006. (Twelve pages, no pagination.) [AdW, RaC]

  90. Approximation Algorithms for Scheduling on Multiple Machines, with V. S. A. Kumar, M. V. Marathe, and S. Parthasarathy. Proc. IEEE Symposium on Foundations of Computer Science (FOCS), pages 254-263, 2005. [ApA, RaC, ReS, RoM]

  91. Scheduling on Unrelated Machines under Tree-Like Precedence Constraints, with V. S. A. Kumar, M. V. Marathe, and S. Parthasarathy. Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Lecture Notes in Computer Science, Vol. 3624, pages 146-157, 2005. Full version invited to the special issue of Algorithmica dedicated to selected papers from APPROX 2005. [ApA, RaC, ReS, RoM]

  92. Efficient Lookup on Unstructured Topologies, with R. Morselli, B. Bhattacharjee, and M. Marsh. Proc. ACM Symposium on Principles of Distributed Computing (PODC), pages 77-86, 2005. Extended version available as Technical Report CS-TR-4772. [DiP, InW, RaC]

  93. Algorithmic Aspects of Capacity in Wireless Networks, with V. S. A. Kumar, M. V. Marathe, and S. Parthasarathy. Proc. ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), pages 133-144, 2005. [AdW, ApA, RoA]

  94. Provable Algorithms for Parallel Sweep Scheduling on Unstructured Meshes, with V. S. A. Kumar, M. V. Marathe, S. Parthasarathy, and S. Zust. Proc. International Parallel and Distributed Processing Symposium (IPDPS), 2005. [ApA, DiP, RaC, ReS]

  95. Cost-Sharing Mechanisms for Network Design, with A. Gupta and É. Tardos. Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 139-150, 2004. (Extended Version, July 2005.) [ApA, EC, RaC]

  96. Scalable Resilient Media Streaming, with S. Banerjee, S. Lee, R. Braud, and B. Bhattacharjee. Proc. ACM International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV), pages 4-9, 2004. [DiP, InW, RaC]

  97. End-to-End Packet-Scheduling in Wireless Ad-Hoc Networks, with V. S. A. Kumar, M. V. Marathe, and S. Parthasarathy. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1014-1023, 2004. [AdW, DiP, RaC, ReS]

  98. Structural and Algorithmic Aspects of Massive Social Networks, with S. Eubank, V. S. A. Kumar, M. V. Marathe, and N. Wang. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 711-720, 2004. [DaS, PHe, RaC, SoN]

  99. On the Covering Steiner Problem, with A. Gupta. Proc. Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST & TCS), pages 244-251, 2003. [ApA, RaC, RoM]

  100. Approximation Algorithms for Channel Allocation Problems in Broadcast Networks, with R. Gandhi, S. Khuller, and N. Wang. Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 47-58, 2003. [ApA, DiP, RaC]

  101. An Improved Approximation Algorithm For Vertex Cover with Hard Capacities, with R. Gandhi, E. Halperin, S. Khuller, and G. Kortsarz. Proc. International Colloquium on Automata, Languages, and Programming (ICALP), pages 164-175, 2003. [ApA, RaC, RoM]

  102. Resilient Multicast using Overlays, with S. Banerjee, S. Lee, and B. Bhattacharjee. Proc. ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), pages 102-113, 2003. [DiP, InW, RaC]

  103. Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons, with D. Dubhashi, A. Mei, A. Panconesi, and J. Radhakrishnan. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 717-724, 2003. [AdW, DiP, RaC]

  104. Integrality Ratio for Group Steiner Trees and Directed Steiner Trees, with E. Halperin, G. Kortsarz, R. Krauthgamer, and N. Wang. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 275-284, 2003. [ApA, RaC, RoM]

  105. Dependent Rounding in Bipartite Graphs, with R. Gandhi, S. Khuller, and S. Parthasarathy. Proc. IEEE Symposium on Foundations of Computer Science (FOCS), pages 323-332, 2002. [ApA, RaC, RoM]

  106. Improved Approximation Algorithms for the Partial Vertex Cover Problem, with E. Halperin. Proc. Fifth International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 161-174, 2002. [ApA, RaC, RoM]

  107. P5: A Protocol for Scalable Anonymous Communication, with R. Sherwood and B. Bhattacharjee. Proc. IEEE Symposium on Security and Privacy, pages 58-70, 2002. [InW, RaC]

  108. Clustering and Server Selection using Passive Monitoring, with M. Andrews, B. Shepherd, P. Winkler, and F. Zane. Proc. IEEE Conference on Computer Communications (INFOCOM), Volume 3, pages 1717-1725, 2002. [InW]

  109. Distributions on Level-Sets with Applications to Approximation Algorithms. Proc. IEEE Symposium on Foundations of Computer Science (FOCS), pages 588-597, 2001. [ApA, InW, RaC, RoA, RoM]

  110. Efficient Algorithms for Location and Sizing Problems in Network Design, with K. Kumaran, S. Lanning, K. G. Ramakrishnan, and Q. Wang. Proc. IEEE Global Communications Conference (GLOBECOM), pages 2586-2590, 2001. [InW]

  111. Finding Large Independent Sets of Hypergraphs in Parallel, with H. Shachnai. Proc. ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 163-168, 2001. [DiP, RaC]

  112. Experimental Analysis of Algorithms for Bilateral-Contract Clearing Mechanisms Arising in Deregulated Power Industry, with C. Barrett, D. Cook, V. Faber, G. Hicks, A. Marathe, M. V. Marathe, Y. J. Sussmann, and H. Thornquist. Proc. Workshop on Algorithm Engineering (WAE), pages 172-184, 2001.

  113. Approximation Algorithms for Partial Covering Problems, with R. Gandhi and S. Khuller. Proc. International Colloquium on Automata, Languages, and Programming (ICALP), pages 225-236, 2001. [Full Version] [ApA, RaC, RoM]

  114. New Approaches to Covering and Packing Problems. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 567-576, 2001. [ApA, DiP, RaC, RoM]

  115. Domatic Partitions and the Lovász Local Lemma. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 922-923, 2001. [ApA, RaC]

  116. Wavelength Rerouting in Optical Networks, or the Venetian Routing Problem, with A. Caprara, G. Italiano, G. Mohan, and A. Panconesi. Proc. Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 72-83, 2000. [ApA, InW]

  117. The Value of Strong Inapproximability Results for Clique. Proc. ACM Symposium on Theory of Computing (STOC), pages 144-152, 2000. [ApA, RaC]

  118. Optimal Design of Signaling Networks for Internet Telephony, with K. G. Ramakrishnan, K. Kumaran, M. Aravamudan, and S. Naqvi. Proc. IEEE Conference on Computer Communications (INFOCOM), pages 707-716, 2000. [InW, RaC]

  119. Improved Bounds on the Sample Complexity of Learning, with Y. Li and P. M. Long. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 309-318, 2000. [MLe]

  120. Application-layer Broker for Scalable Internet Services with Resource Reservation, with P. Bai and B. Prabhakaran. Proc. Seventh ACM Multimedia Conference (MM '99), pages 103-106, 1999. (Poster paper.) [InW, ReS]

  121. Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families, with M. Saks, S. Zhou, and D. Zuckerman, Proc. Third International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pages 11-15, 1999. [InW, RaC]

  122. New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning, with F. T. Leighton and S. B. Rao, Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 643-652, 1999. [ApA, InW, RaC, RoA, RoM]

  123. Improved Bounds and Algorithms for Hypergraph Two-coloring, with J. Radhakrishnan, Proc. IEEE Symposium on Foundations of Computer Science (FOCS), pages 684-693, 1998. [GrC, RaC]

  124. Low-bandwidth Routing and Electrical Power Networks, with D. Cook, V. Faber, M. V. Marathe, and Y. J. Sussmann, Proc. International Colloquium on Automata, Languages, and Programming (ICALP), pages 604-615, 1998. [ApA, RaC, RoA, RoM]

  125. Multicommodity Flow and Circuit Switching, with F. T. Leighton and S. B. Rao, Proc. Hawaii International Conference on System Sciences (HICSS), pages 459-465, 1998. [ApA, InW, RaC, RoM]

  126. Improved Approximations for Edge-disjoint Paths, Unsplittable Flow, and Related Routing Problems, Proc. IEEE Symposium on Foundations of Computer Science (FOCS), pages 416-425, 1997. [ApA, InW, RaC, ReS, RoA, RoM]

  127. Mechanism Design for Intellectual Property Rights Protection, with P. S. Giridharan, Proc. International Conference on Information Systems (ICIS), 1997. [EC]

  128. Approximating Hyper-Rectangles: Learning and Pseudo-Random Sets, with P. Auer and P. M. Long, Proc. ACM Symposium on Theory of Computing (STOC), pages 314-323, 1997. [MLe, RaC]

  129. A Constant-Factor Approximation Algorithm for Packet Routing, and Balancing Local vs. Global Criteria, with C. P. Teo, Proc. ACM Symposium on Theory of Computing (STOC), pages 636-643, 1997. [ApA, InW, RoA, RoM]

  130. Better Approximation Guarantees for Job-Shop Scheduling, with L. A. Goldberg, M. S. Paterson and E. Sweedyk, Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 599-608, 1997. [ApA, RaC, ReS]

  131. Improving the Discrepancy Bound for Sparse Matrices: Better Approximations for Sparse Lattice Approximation Problems, Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 692-701, 1997. [ApA, GrC, RaC, RoM]

  132. Improved Parallel Approximation of a Class of Integer Programming Problems, with N. Alon, Proc. International Colloquium on Automata, Languages, and Programming (ICALP), pages 562-573, 1996. [DiP, RaC, RoM]

  133. An Extension of the Lovász Local Lemma, and its Applications to Integer Programming, Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 6-15, 1996. [Extended Version, April 2005] [ApA, GrC, RaC, RoA, RoM]

  134. Splitters and Near-optimal Derandomization, with M. Naor and L. J. Schulman, Proc. IEEE Symposium on Foundations of Computer Science (FOCS), pages 182-191, 1995. [RaC]

  135. Contention Resolution with Bounded Delay, with M. S. Paterson, Proc. IEEE Symposium on Foundations of Computer Science (FOCS), pages 104-113, 1995. [DaS, DiP, RaC, ReS]

  136. Explicit Dispersers with Polylog Degree, with M. Saks and S. Zhou, Proc. ACM Symposium on Theory of Computing (STOC), pages 479-488, 1995. [RaC]

  137. Improved Approximations of Packing and Covering Problems, Proc. ACM Symposium on Theory of Computing (STOC), pages 268-276, 1995. [ApA, RaC, RoM]

  138. Computing with Very Weak Random Sources, with D. Zuckerman, Proc. IEEE Symposium on Foundations of Computer Science (FOCS), pages 264-275, 1994. [RaC]

  139. Improved Algorithms via Approximations of Probability Distributions, with S. Chari and P. Rohatgi, Proc. ACM Symposium on Theory of Computing (STOC), pages 584-592, 1994. [DiP, RaC]

  140. Randomness-Optimal Unique Element Isolation, with Applications to Perfect Matching and Related Problems, with S. Chari and P. Rohatgi, Proc. ACM Symposium on Theory of Computing (STOC), pages 458-467, 1993. [DiP, RaC]

  141. Chernoff-Hoeffding Bounds for Applications with Limited Independence, with J. P. Schmidt and A. Siegel, Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 331-340, 1993. [RaC, ReS]

  142. Fast Randomized Algorithms for Distributed Edge Coloring, with A. Panconesi, Proc. ACM Symposium on Principles of Distributed Computing (PODC), pages 251-262, 1992. [DiP, GrC, RaC, ReS]

  143. Improved Distributed Algorithms for Coloring and Network Decomposition Problems, with A. Panconesi, Proc. ACM Symposium on Theory of Computing (STOC), pages 581-592, 1992. (Best Student Paper Award.) [DiP, GrC]

Invited Papers and Chapters in Books

  1. Model-Based Forecasting of Significant Societal Events, with N. Ramakrishnan, C.-T. Lu, M. V. Marathe, A. Marathe, A. Vullikanti, S. Eubank, S. C. Leman, M. Roan, J. S. Brownstein, K. Summers, L. Getoor, T. Choudhury, D. Gupta, and D. Mares. IEEE Intelligent Systems, Vol. 30, pages 86-90, 2015. [DaS, MLe, PHe, SoN]

  2. Efficient Booster Pump Placement in Water Networks using Graph Theoretic Principles, with I. Narayanan, V. Sarangan, A. Vasan, A. Sivasubramaniam, B. S. Murty, and S. Narasimhan. Invited short paper, International Green Computing Conference (IGCC), 2012. [SGr]

  3. Local Balancing Influences Global Structure in Social Networks, Proceedings of the National Academy of Sciences, 108(5), pages 1751-1752, 2011. (Invited commentary.) [DaS, SoN]

  4. Minimum Weighted Completion Time, with V. S. A. Kumar, M. V. Marathe, and S. Parthasarathy. Encyclopedia of Algorithms, (M.-Y. Kao, Editor-in-Chief), Springer, 2015. (Previous edition: 2008.) [ApA, RaC, ReS, RoM]

  5. Randomized Algorithms and Probabilistic Analysis in Wireless Networking. Proc. Symposium on Stochastic Algorithms, Foundations, and Applications (SAGA), J. Hromkovic, R. Kralovic, M. Nunkesser, and P. Widmayer (Eds.), Lecture Notes in Computer Science 4665, Springer, pages 54-57, 2007. [AdW, ApA, RaC]

  6. Structure of Social Contact Networks and their Impact on Epidemics, with S. Eubank, V. S. A. Kumar, M. V. Marathe, and N. Wang. AMS-DIMACS Volume on Discrete Methods in Epidemiology, Volume 70, pages 181-214, 2006. [DaS, PHe, RaC, SoN]

  7. Combinatorial Problems Arising in Deregulated Electrical Power Industry: Survey and Future Directions, with D. Cook, G. Hicks, V. Faber, M. V. Marathe, Y. J. Sussmann, and H. Thornquist, Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems (P. M. Pardalos, Editor), Kluwer Academic Publishers, pages 138-162, 2000. [ApA, RaC, RoA]

  8. Low-discrepancy Sets for High-Dimensional Rectangles: A Survey, Bulletin of the European Association for Theoretical Computer Science, Number 70, pages 67-76, 2000. [RaC]

  9. A Survey of the Role of Multicommodity Flow and Randomization in Network Design and Routing, Randomization Methods in Algorithm Design (P. M. Pardalos, S. Rajasekaran and J. Rolim, editors), American Mathematical Society, Series in Discrete Mathematics and Theoretical Computer Science, Volume 43, pages 271-302, 1999. [ApA, InW, RaC, RoA, RoM]

  10. Approximation Algorithms via Randomized Rounding: a Survey. Lectures on Approximation and Randomized Algorithms (M. Karonski and H. J. Promel, editors), Series in Advanced Topics in Mathematics, Polish Scientific Publishers PWN, Warszawa, pages 9-71, 1999. [ApA, InW, RaC, RoA, RoM]

  11. Scheduling and Load-Balancing via Randomization, Proc. Pre-Conference Workshop on Randomized Algorithms, Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 1997. [RaC, ReS]

  12. The Role of Randomness in Computation, BRICS Notes Series NS-95-6, Basic Research Institute in Computer Science, Denmark, 1995. [RaC]

Technical Reports and Theses

  1. Improved Approximation Algorithms for Stochastic-Matching Problems, with M. Adamczyk, B. Brubach, F. Grandoni, K. A. Sankararaman, and P. Xu. Technical Report, arXiv, 2020. [ApA, DaS, KEx, PHe, RaC, RoM]

  2. LP-rounding algorithms for facility-location problems, with J. Byrka and M. R. Ghodsi. Technical Report, arXiv, 2010. [ApA, RaC, ReS, RoM]

  3. A Scalable Algorithm for the Minimum Expected Cost Restorable Flow Problem, with L. Fleischer, A. Meyerson, I. Saniee, and B. Shepherd. CORC Technical Report TR-2003-10, Computational Optimization Research Center, Columbia University, 2003. [ApA, InW, ReS, RoA]

  4. Techniques for Probabilistic Analysis and Randomness-Efficient Computation, TR 93-1378, Department of Computer Science, Cornell University, 1993. [DiP, GrC, RaC, ReS]

  5. A Generalization of Brooks' Theorem, TR 92-1302, Department of Computer Science, Cornell University, 1992. [DiP, GrC]

  6. Fast Algorithms for Some Problems on Interval and Permutation Graphs, B. Tech. Thesis, Department of Computer Science and Engineering, Indian Institute of Technology, Chennai, 1989.

Additional Papers

  1. Bottom of the Pyramid: Served "by" the world's poor profitably? (A Social Networks Approach for Sustainable Poverty Alleviation), with S. Shivarajan. First CR3 Conference (on Corporate Responsibility/Global Responsibility), 2011. [SGr, SoN]

  2. A Note on the Distribution of the Number of Prime Factors of Integers. Presented at the Hawaii International Conference on Statistics, Mathematics, and Related Fields, 2005. [RaC]

  3. The Discrepancy of Permutation Families, with J. H. Spencer and P. Tetali. Unpublished manuscript, 2001. (See here for some exciting progress by Newman and Nikolov in the year 2011.) [RaC, RoM]

Back to Aravind Srinivasan's Home Page