On-line
Steiner trees in the Euclidean plane
N. Alon, Y. Azar.
Proc. of 8th Computational Geometry (1992), 337-343. Also in Discrete and
Computational Geometry 10 (1993), 113-121.
While the above paper presents simple proofs, the main
result is originally due to Imase and Waxman, who also present the lower bound
sketched in class. Makoto Imase, Bernard M. Waxman: Dynamic Steiner Tree
Problem. SIAM Journal on Discrete Mathematics 4(3): 369-384 (1991)
D.M. Andrews, B. Awerbuch, A. Fernandez, J. Kleinberg, F.T. Leighton, Z. Liu. Universal stability results for greedy contention-resolution protocols. Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996.
A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan, D. Williamson. Adversarial queueing theory. Proc. 28th ACM Symposium on Theory of Computing, 1996.a
Addititional reading (optional):
A.
Goel. Stability of Networks
and Protocols in the Adversarial Queueing Model for Packet Routing .
ACM-SIAM Symposium on Discrete Algorithms, 1999 (short abstract). Accepted for
publication in Networks.
Xinming He’s solution to the HW problem on stability.
"Achieving 100%
Throughput in an Input-Queued Switch"
Nick McKeown, Venkat Anantharam and Jean Walrand
Proceedings of IEEE Infocom '96, Vol 1, pp. 296-302, San Francisco, March
1996.
"Matching Output
Queueing with a Combined Input Output Queued Switch ." Shang-Tse
Chuang, Ashish Goel, Nick McKeown, Balaji Prabhakar
Computer Systems Technical Report CSL-TR-98-758. March 1998.
Also published in: Proceedings of INFOCOM '99, 1169-1178, IEEE, April 1999,
and
IEEE Journal on Selected Areas in Communications, vol.17, n.6, Dec.1999, pp.
1030-1039.
Competitive
Routing of Virtual Circuits in ATM networks.
S. Plotkin.
Survey, invited paper to IEEE J. Selected Areas in
Communications.
Focus on sections 1, 2, and 3.
Supplemental Reading (to complete some of the proofs in
the above):
On-line
machine scheduling with applications to load balancing
and virtual circuit routing.
J. Aspnes, Y. Azar, A. Fiat, S.
Plotkin, and O. Waarts.
Full version of the STOC 1993 paper.
Throughput
competitive on-line routing.
B. Awerbuch, Y. Azar,
and S. Plotkin.
In FOCS 1993.
Feb 14, 19, 21, 26,
28: Multicommodity Flows and Integer Routing
Fast approximation algorithms for fractional packing and covering problems.
S. Plotkin, D. Shmoys, and E. Tardos.
Math of Oper. Res. 1995. Preliminary version in FOCS 1991
N.Garg, J.Könemann Faster and Simpler
Algorithms for Multicommodity Flow and other Fractional Packing Problems ;
FOCS 1998.
Prabhakar Raghavan and Clark
D. Thompson.
Randomized Rounding: A technique
for provably good algorithms and algorithmic proofs, Combinatorica, Vol.
7, 1987.
Mar 5, 7, 19: Approximate Fairness, Approximate Majorization
Using
approximate majorization to characterize protocol fairness.
R. Bhargava, A. Goel, A. Meyerson.
Full
version of a paper that appeared in Sigmeterics 2001 as a short abstract.
Rate control in communication networks: shadow prices, proportional fairness and stability
F. P. Kelly, A.K. Maulloo and D.K.H. Tan.
Journal of the Operational Research Society 49
(1998), 237-252.
(skip
the proofs in this paper)
Mar 26, 28: Bartal’s tree embeddings, implications, aggregation, and buy-at-bulk.
The first of the following two papers offers more intuition, and is suggested reading. The second offers the better result but is more technical; just read the abstract.
Probabilistic
Approximation of Metric Spaces and its Algorithmic Applications
Y. Bartal.
In Proc. of the 37th Ann. IEEE Symp. on Foundations of Computer Science,
October 1996.
On Approximating
Arbitrary Metrics by Tree Metrics
Y. Bartal.
In Proc. of the 30th Ann. ACM Symp. on Theory of Computing, May 1998.
Buy-at-bulk network design
B. Awerbuch, Y. Azar.
Proc. of 38th FOCS (1997), 542-547.
Algorithmic
Mechanism Design
by N. Nisan and A. Ronen. Expanded version of the paper that appeared in STOC
1999.
T. Roughgarden and E. Tardos. How Bad is Selfish Routing? Appeared in FOCS 2000, pages 93--102. Full version (revised 12/5/01) to appear in JACM.
Joan Feigenbaum, Christos Papadimitriou, and Scott Shenker. Sharing the Cost of Multicast Transmissions. In Thirty-Second Annual ACM Symposium on Theory of Computing (STOC00), May 2000.
Apr 18, 25: Peer-to-Peer Systems:
A Scalable Content-Addressable Network
Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp,
Scott Shenker
In Proceedings of ACM SIGCOMM 2001
Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications
"Chord: A Scalable Peer-to-peer Lookup Service for
Internet Applications",
Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari
Balakrishnan, in
Proceedings of ACM SIGCOMM'01, San Diego, September 2001.
Using the small world model to improve Freenet performance
Zhang, Goel, Govindan.
J. Kleinberg. The small-world phenomenon: An algorithmic perspective.
Proc. 32nd ACM Symposium on Theory of Computing, 2000
Accessing Nearby Copies of Replicated Objects in a
Distributed Environment
Plaxton, Rajaraman, Richa.