Aravind Srinivasan's List of Publications

Some of the research reported below has been supported in part by the National Science Foundation, IARPA, and the U.S. Army Research Office. I am grateful to these agencies for their 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 agencies or of 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
DiP = Distributed/Parallel Algorithms GaT = Game Theory, Mechanism Design, Auctions
GrC = Graph/Hypergraph Coloring InW = Internet/WWW-related
MLe = Machine Learning 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. 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. [RaC]

  2. The Moser-Tardos Framework with Partial Resampling, with D. G. Harris. (This is a full version that combines our papers from STOC 2013 and FOCS 2013.) [ApA, InW, RaC, RoA, RoM]

  3. 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]

  4. 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]

  5. 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, RaC, ReS, RoM]

  6. 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]

  7. 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]

  8. 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]

  9. 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]

  10. 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. [PHe, RaC, SoN]

  11. 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. [DiP, InW, RaC, ReS]

  12. 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]

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

  14. 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]

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

  16. 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. 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, accepted for publication. [AdW, SGr, SoN]

  2. A Note on Near-Optimal Coloring of Shift Hypergraphs, with D. G. Harris. Accepted for publication, Random Structures & Algorithms. [GrC, RaC]
  3. 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, accepted for publication. [AdW, PHe, RaC, SoN]

  4. On Random Sampling Auctions for Digital Goods, with S. Alaei and A. Malekian. ACM Transactions on Economics and Computation, to appear. [GaT, RaC]

  5. 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]

  6. 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]

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

  8. 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. [RaC, SoN]

  9. 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]

  10. 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]

  11. 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]

  12. 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]

  13. 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, RaC, ReS, RoM]

  14. 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]

  15. 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]

  16. 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]

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

  18. 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]

  19. 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]

  20. 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]

  21. 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]

  22. 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]

  23. 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]

  24. 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]

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

  26. 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]

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

  28. 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]

  29. 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. [PHe, RaC, SoN]

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

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

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

  33. 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]

  34. 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.

  35. 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]

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

  37. 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]

  38. 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]

  39. 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]

  40. 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]

  41. 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]

  42. 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]

  43. 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. [DiP, InW, RaC, ReS]

  44. 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]

  45. 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]

  46. 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]

  47. 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]

  48. 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]

  49. 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]

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

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

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

  53. 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]

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

  55. 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]

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

  57. 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]

  58. 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]

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

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

  61. 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. 'Beating the news' with EMBERS: Forecasting Civil Unrest using Open Source Indicators, with N. Ramakrishnan et al. To appear, Proc. ACM Conference on Knowledge Discovery and Data Mining (KDD), 2014. [MLe, SoN]

  2. 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]

  3. 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. [RaC]

  4. 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 version fixes these errors.) [ApA, RaC]

  5. 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]

  6. 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]

  7. 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]

  8. 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]

  9. 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]

  10. 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.) [SGr, SoN]

  11. 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]

  12. 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]

  13. 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. [PHe, RaC, SoN]
  14. 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]
  15. 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.) [InW, MLe, RaC, SoN]
  16. 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]

  17. 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]

  18. 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]

  19. 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]

  20. 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]

  21. 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 Theoreical Computer Science) in 2011, is an exciting new forum aiming to be a high-quality conference in theoretical computer science.) [ApA, RaC, ReS, RoM]

  22. 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.) [InW, RaC, SoN]

  23. 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. [InW, RaC, SoN]

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

  25. 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]

  26. 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]

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

  28. 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]

  29. 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]

  30. 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]

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

  32. 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]

  33. 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]

  34. 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]

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

  36. 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]

  37. 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]

  38. 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]

  39. 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]

  40. 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]

  41. 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]

  42. 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]

  43. 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, GaT, RaC]

  44. 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]

  45. 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]

  46. 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. [PHe, RaC, SoN]

  47. 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]

  48. 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]

  49. 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]

  50. 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]

  51. 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]

  52. 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]

  53. 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]

  54. 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]

  55. 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]

  56. 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]

  57. 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]

  58. 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]

  59. 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]

  60. 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.

  61. 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]

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

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

  64. 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]

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

  66. 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]

  67. 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]

  68. 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]

  69. 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]

  70. 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]

  71. 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]

  72. 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]

  73. 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]

  74. 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]

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

  76. 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]

  77. 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]

  78. 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]

  79. 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]

  80. 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]

  81. 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]

  82. 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]

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

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

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

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

  87. 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]

  88. 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]

  89. 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]

  90. 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]

  91. 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. 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]

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

  3. 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, 2008. [ApA, RaC, ReS, RoM]

  4. 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]

  5. 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. [PHe, RaC, SoN]

  6. 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]

  7. 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]

  8. 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]

  9. 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]

  10. 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]

  11. 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. LP-rounding algorithms for facility-location problems, with J. Byrka and M. R. Ghodsi. Technical Report, arXiv, 2010. [ApA, RaC, ReS, RoM]

  2. 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]

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

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

  5. 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