The documents listed below have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Publications

Coupled and k-sided placements: Generalizing generalized assignment
with M. Korupolu, A. Meyerson, and B. Tagiku
IPCO, June 2014

Network effects of risk behavior change following prophylactic interventions
with V. Anil Kumar, Zhifeng Sun, and Ravi Sundaram
PLoS ONE, August 2013

Branching Random Walks on Graphs
with Chinmoy Dutta, Gopal Pandurangan, and Scott Roche
ACM SPAA 2013

On the Complexity of Information Spreading in Dynamic Networks
with Chinmoy Dutta, Gopal Pandurangan, Zhifeng Sun, and Emanuele Viola
ACM-SIAM SODA 2013

Split and Join: Strong Graph Partitions and Universal Steiner Trees for Graphs
with C. Busch, C. Dutta, J. Radhakrishnan, and S. Srinivasagopalan
IEEE FOCS 2012

Discovery Through Gossip
with Bernhard Haeupler, Gopal Pandurangan, David Peleg, and Zhifeng Sun
ACM SPAA 2012

Cache me if you can: Capacitated Selfish Replication Games
with R. Gopalakrishnan, D. Kanoulas, N. Karuturi, C. Pandu Rangan, and R. Sundaram
LATIN 2012.

On the robustness of IEEE 802.11 rate adaptation algorithms against smart jamming
with Guevara Noubir, Bo Sheng, and Bishal Thapa
ACM WISEC 2011, winner of best paper award

Multicommodity Facility Location under Group Steiner Access Cost
with Laura Poplawski
SODA 2011.

Existence Theorems and Approximation Algorithms for Generalized Network Security Games
with A. Kumar, Z. Sun, and R.Sundaram
ICDCS 2010.

A General Framework for Incremental Approximation and Hierarchical Clustering
with G. Lin and C. Nagarajan and D. Williamson. 
SICOMP 2010, preliminary version in SODA 2006.

Approximation Algorithms for Multiprocessor Scheduling under Uncertainty
with G. Lin
Theory of Computing Systems 2010, special issue on selected papers from on SPAA 2007.

Reducibility among Fractional Stability Problems
with S. Kintali, L. Poplawski, R.Sundaram, and S. Teng
FOCS 2009.

Approximation Algorithms for Key Management in Secure Multicast
with A. Chan, Z. Sun, and F. Zhu
COCOON 2009.

Bounded 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
PODC 2008.

Approximation Algorithms for Data Placement Problems
with I. Baev, and C. Swamy
SIAM Journal on Computing, 2008.

On the Performance of IEEE 802.11 under Jamming
with E. Bayrataroglu, C. King, X. Liu, G. Noubir, and B. Thapa
In Proceedings of Infocom 2008

(Almost) 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 Sensor Networks
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.

Playing Push vs Pull: Models and Algorithms for Disseminating Dynamic Data in Networks
with R. Chakinala, A. Kumarasubramanian, K. Laing, R. Manokaran, and P. Rangan
SPAA 2006.

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.

Compact 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

Group-Independent 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

Universal Approximations for Steiner Tree, TSP, and Set Cover
with L. Jia, G. Lin, G. Noubir, and R. Sundaram
STOC 2005.

Multi-Query Optimization for Sensor Networks
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

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

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

Near-Optimal 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

On Local Algorithms for Topology Control and Routing in Ad hoc Networks
with L. Jia and C. Scheideler
In SPAA 2003

Time-Constrained 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.

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

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

Topology Control and Routing in Ad hoc Networks: A Survey
In SIGACT News 33:60-73, June 2002

A Data Tracking Scheme for General Networks
with A.W. Richa, B. Vöcking, and G. Vuppuluri.
SPAA 2001.

Approximation Algorithms for Data Placement in Arbitrary Networks
with I. Baev.
SODA 2001.

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

Towards More Complete Models of TCP Latency and Throughput
with M. Mitzenmacher.
Journal of Supercomputing 20:137--160,  2001.  Special issue on transport protocols.

Analysis of 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.

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

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

A Dynamic Object Replication and Migration Protocol for an Internet Hosting Service
with M. Rabinovich, I. Rabinovich, and A. Aggarwal.
In ICDCS 1999.

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

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

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

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

Dissertation

Sharing Resources in Distributed Systems, December 1997.