Network effects of risk behavior change following prophylactic
with V. Anil Kumar, Zhifeng Sun, and Ravi Sundaram
Manuscript, April 2012
Branching Random Walks on Graphs
with Chinmoy Dutta, Gopal Pandurangan, and Scott Roche
Manuscript, February 2012
On the Complexity of Information Spreading in Dynamic Networks
with Chinmoy Dutta, Gopal Pandurangan, Zhifeng Sun, and Emanuele Viola
to appear at SODA 2013
Split and Join: Strong Graph Partitions and Universal Steiner Trees
with C. Busch, C. Dutta, J. Radhakrishnan, and S. Srinivasagopalan
To appear in FOCS 2012
with Bernhard Haeupler, Gopal Pandurangan, David Peleg, and Zhifeng Sun
ACM SPAA 2012, to appear.
Cache me if you can: Capacitated
Selfish Replication Games
with R. Gopalakrishnan, D. Kanoulas, N. Karuturi, C. Pandu Rangan, and R. Sundaram
robustness of IEEE 802.11 rate adaptation algorithms against smart
with Guevara Noubir, Bo Sheng, and Bishal Thapa
ACM WISEC 2011, winner of best paper award
Facility Location under Group Steiner Access Cost
with Laura Poplawski
Theorems and Approximation Algorithms for Generalized Network Security Games
with A. Kumar, Z. Sun, and R.Sundaram
General Framework for Incremental Approximation and Hierarchical
with G. Lin and C. Nagarajan and D. Williamson.
SICOMP 2010, preliminary version in SODA 2006.
Algorithms for Multiprocessor Scheduling under
with G. Lin
Theory of Computing Systems 2010, special issue on selected papers from on SPAA 2007.
among Fractional Stability Problems
with S. Kintali, L. Poplawski, R.Sundaram, and S. Teng
Algorithms for Key Management in Secure Multicast
with A. Chan, Z. Sun, and F. Zhu
Budget Connection Games, or How to Make Friends and Influence People, on a Budget
with N. Laoutaris, L. Poplawski, R. Sundaram, and S.-H. Teng
Algorithms for Data Placement Problems
with I. Baev, and C. Swamy
SIAM Journal on Computing, 2008.
Performance of IEEE 802.11 under Jamming
with E. Bayrataroglu, C. King, X. Liu, G. Noubir, and B. Thapa
In Proceedings of Infocom 2008
Tight Bounds and Existence Theorems for Single-Commodity Confluent Flows
with J. Chen, R. Kleinberg, L. Lovasz, R. Sundaram, and A. Vetta.
In Journal of the ACM, volume 54, 2007
A preliminary version appears in STOC 2004.
A Space Lower
Bound for Name-Independent Compact Routing in Trees
with K. Laing
Journal of Interconnection Networks, volume 8, September 2007.
Wave Scheduling and Routing in
with A. Trigoni, Y. Yao, A. Demers, and J. Gehrke.
In ACM Transactions on Sensor Networks, volume 3, March 2007.
A preliminary version appears in DMSN 2004 a VLDB 2004 workshop.
Push vs Pull: Models and Algorithms for Disseminating Dynamic Data in
with R. Chakinala, A. Kumarasubramanian, K. Laing, R. Manokaran, and P. Rangan
On the Confluent Capacity of the Internet: Congestion and Dilation
with J. Chen, M. Marathe, and R. Sundaram
ICDCS 2006; winner of best paper award
Meet and Merge: Approximation Algorithms for Confluent Flows
with J. Chen and R. Sundaram.
Journal of Computer and System Sciences, 72(3): 468-489 (2006)
A preliminary version appears in STOC 2003.
Routing with Name Independence
with M. Arias, L. Cowen, K. Laing, and O. Taka
SIAM Journal on Discrete Mathematics, volume 20, pages 705--726, 2006
A preliminary version appears in SPAA 2003
Spanning Trees for Data
Aggregation in Sensor Networks
with L. Jia, G. Noubir, and R. Sundaram
In IEEE International Conference on Distributed Computing in Sensor Systems, June 2006
Approximations for Steiner Tree, TSP, and Set Cover
with L. Jia, G. Lin, G. Noubir, and R. Sundaram
with N. Trigoni, Y. Yao, A. Demers, and J. Gehrke
In IEEE International Conference on Distributed Computing in Sensor Systems, June-July 2005
Hybrid Push-Pull Query Processing for Sensor Networks
with N. Trigoni, Y. Yao, A. Demers, and J. Gehrke
In GI-Conference Informatik Workshop on Sensor Networks. Berlin, Germany, September 2004.
Mobility Models for Ad Hoc Networks
with G. Lin and G. Noubir
In Proceedings of INFOCOM, March 2004
Algorithms for Stretch Scheduling
with M. Bender and S. Muthukrishnan.
In Journal of Scheduling 7(3): 195-222 (2004)
A preliminary version appears in SODA 2002.
to Minimize Average Stretch
with J. E. Gehrke, S. Muthukrishnan, and A. Shaheen
In SIAM Journal on Computing, 34(2): 433-452 (2004)
A preliminary version appears in FOCS 1999.
Hardness Results and Approximation Algorithms for Edge-Disjoint Paths
and Related Problems
with V. Guruswami, S. Khanna, B. Shepherd, and M. Yannakakis.
In Journal of Computer and System Sciences, 67(3), 473-496, 2003
A preliminary version appears in STOC 1999.
The Cougar Project: A Work-In-Progress Report
with A. Demers, J. Gehrke, N. Trigoni, and Y. Yao
Sigmod Record, Volume 34, Number 4, December 2003
Algorithms for Topology Control and Routing in Ad hoc Networks
with L. Jia and C. Scheideler
In SPAA 2003
Scheduling of Weighted Packets on Trees and Meshes
with M. Adler, S. Khanna, and A. Rosen.
In Algorithmica, 36(2): 123--152, 2003
A preliminary version appears in SPAA 1999.
Efficient Distributed Algorithm for Constructing Small Dominating Sets
with L. Jia and T. Suel.
In Distributed Computing 15:193-205, 2002.
Special issue on selected papers from PODC 2001.
Adversarial Model for Distributed Dynamic Load Balancing
with S. Muthukrishnan.
In Journal of Interconnection Networks 3:35--47, 2002.
A preliminary version appears in SPAA 1998.
Control and Routing in Ad hoc Networks: A Survey
In SIGACT News 33:60-73, June 2002
Data Tracking Scheme for General Networks
with A.W. Richa, B. Vöcking, and G. Vuppuluri.
Algorithms for Data Placement in Arbitrary Networks
with I. Baev.
Algorithms for Hierarchical Cooperative Caching
with M. R. Korupolu and C. G. Plaxton.
In Journal of Algorithms 38:260--302, 2001.
Special issue on selected papers from SODA 1999.
Complete Models of TCP Latency and Throughput
with M. Mitzenmacher.
Journal of Supercomputing 20:137--160, 2001. Special issue on transport protocols.
a Local Search Heuristic for Facility Location Problems
with M. Korupolu and C. G. Plaxton.
In Journal of Algorithms 37:146--188, 2000.
Special issue on selected papers from SODA 1998.
Convergence of a Local Load Balancing Algorithm for Asynchronous Rings
with J. E. Gehrke and C. G. Plaxton.
In Theoretical Computer Science 220(1):247-265, 1999.
A preliminary version appears in DISC 1997.
Analyses of Two Local Load Balancing Algorithms
with B. Ghosh, F. T. Leighton, B. M. Maggs, S. Muthukrishnan, C. G. Plaxton, A. W. Richa, R. E. Tarjan, and D. Zuckerman.
In SIAM Journal on Computing, 29(1):29-64, 1999.
A preliminary version appears in STOC 1995.
Object Replication and Migration Protocol for an Internet Hosting
with M. Rabinovich, I. Rabinovich, and A. Aggarwal.
In ICDCS 1999.
Nearby Copies of Replicated Objects in a Distributed Environment
with C. G. Plaxton and A. W. Richa.
In Theory of Computing Systems 32:241-280, 1999.
Special issue on selected papers from SPAA 1997.
Contention Resolution Protocols and Associated Probabilistic Phenomena
with P. D. Mackenzie and C. G. Plaxton.
In Journal of the ACM 45(2):324-378, March 1998.
A preliminary version appears in STOC 1994.
Fault-Tolerant Concurrent Access to Shared Objects
with C. G. Plaxton.
In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, pages 570-579, October 1996.
Clustering for Delay Minimization
with D. F. Wong.
In IEEE Transactions on Computer-Aided Design of Intergrated Circuits and Systems , 14(1), pages 1490-1495, December 1995.
A preliminary version appears in Proceedings of the 30th Design Automation Conference, pages 309-314, June 1993.