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.

Approximation Algorithms and Combinatorial Optimization

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

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

Approximation Algorithms for Multiprocessor Scheduling under Uncertainty
with G. Lin
In Proceedings of the 18th Annual ACM Symposium on Parallel Algorithms and Architectures, June 2007

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
In Proceedings of the 18th Annual ACM Symposium on Parallel Algorithms and Architectures, July 2006

A General Framework for Incremental Approximation and Hierarchical Clustering
with G. Lin and C. Nagarajan and D. Williamson. 
In Proceedings of the 17th ACM/SIAM Symposium on Discrete Algorithms, January 2006.

Universal Approximations for Steiner Tree, TSP, and Set Cover
with L. Jia, G. Lin, G. Noubir, and R. Sundaram
In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, June 2005.

(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 Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 529-538, June 2004.

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 Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 373-382, June 2003.

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 Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pages 19-28, May 1999.

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.
A preliminary version appears in Proceedings of the 9th Symposium on Discrete Algorithms, pages 1-10, January 1998.

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.

Ad Hoc and Sensor Networks

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, to appear.

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

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 Proceedings of the Workshop on Sensor Networks as part of the GI-Conference Informatik 2004. Berlin, Germany, September 2004.

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 Proceedings of the International Workshop on Data Management for Sensor Networks (DMSN 2004) held in conjunction with VLDB 2004.

Mobility Models for Ad Hoc Networks
with G. Lin and G. Noubir
In Proceedings of INFOCOM, March 2004

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 Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 220-229, June 2003

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

Distributed Network Algorithms

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
In Proceedings of the ACM Symposium on Principles of Distributed Computing, August 2008, to appear

On the Confluent Capacity of the Internet: Congestion and Dilation
with J. Chen, M. Marathe, and R. Sundaram
In Proceedings of the IEEE International Conference on Distributed Computing and Systems, July 2006

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 Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 184-192, June 2003

An Efficient Distributed Algorithm for Constructing Small Dominating Sets
with L. Jia and T. Suel. 
In Distributed Computing 15:193-205, 2002.
A preliminary version appears in Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, pages 33-42, August 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 Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 47-54, June 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 Proceedings of the 11th International Workshop on Distributed Algorithms, pages 81-95, September 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 Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pages 548-558, May 1995.

Scheduling

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 Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 762-771, January 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 Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pages 433--442, October 1999.

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 Proceedings of the 11th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 1-10, June 1999.

Caching and Replication

A Data Tracking Scheme for General Networks
with A.W. Richa, B. Vöcking, and G. Vuppuluri.
In Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 247--254, July 2001.

Approximation Algorithms for Data Placement in Arbitrary Networks
with I. Baev.
In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 661-670, January 2001.

A Dynamic Object Replication and Migration Protocol for an Internet Hosting Service
with M. Rabinovich, I. Rabinovich, and A. Aggarwal.
In Proceedings of the 19th ACM/IEEE International Conference on Distributed Computing and Systems, June 1999.

Placement Algorithms for Hierarchical Cooperative Caching
with M. R. Korupolu and C. G. Plaxton. 
In Journal of Algorithms 38:260--302, 2001.
A preliminary version appears in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 586-595, January 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.
A preliminary version appears in Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 311-320, June 1997.

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.

Analysis of Network Protocols

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

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 Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 153-162, May 1994.

Dissertation

Sharing Resources in Distributed Systems, December 1997.