1st Max-Planck Advanced Course on the Foundations of Computer Science
Saarbrücken,
Germany, August 31- September 4, 2000
S. Albers, B. von Stengel and R. Werchner, "A combined BIT and TIMESTAMP algorithm for the list update problem", Information Processing Letters, 56:135--139, 1995.
Y. Azar, A. Broder and A. Karlin, "On-line load balancing", 36th IEEE Symp. on Foundations of Computer Science, 218--225, 1992.
S. Ben-David, A. Borodin, R.M. Karp, G. Tardos and A. Wigderson, "On the power of randomization in on-line algorithms", Algorithmica, 11:2-14,1994.
A. Blum, P. Raghavan and B. Schieber, "Navigating in unfamiliar geometric terrain", SIAM Journal on Computing, 26:110-137, 1997.
A. Borodin, S. Irani, P. Raghavan and B. Schieber, "Competitive paging with locality of reference", Journal of Computer and Systems Sciences, 50:244-258, 1995.
A. Borodin, N. Linial and M. Saks, "An optimal on-line algorithm for metrical task systems", Journal of the ACM, 39:745--763, 1992.
R. El-Yaniv, A. Fiat, R.M. Karp and G.Turpin, "Competitive analysis of financial games", 33rd Annual Symp. on Foundations of Computer Science, 327--333, 1992.
A. Fiat, R.M. Karp, L.A. McGeoch, D.D. Sleator and N.E. Young, "Competitive paging algorithms", Journal of Algorithms, 12:685--699, 1991.
E. Koutsoupias and C.H. Papadimitriou, "On the $k$-server conjecture", Journal of the ACM, 42:971-983, 1995.
C.H. Papadimitriou and M. Yannakakis, "Shortest paths without a map", Theoretical Computer Science, 84:127--150, 1991.
N. Reingold, J. Westbrook and D.D. Sleator, "Randomized competitive algorithms for the list update problem", Algorithmica, 11:15--32, 1994.
D. Shmoys, J. Wein and D.P. Williamson, "Scheduling parallel machines on-line", SIAM Journal on Computing, 24:1313-1331, 1995.
D.D. Sleator and R.E. Tarjan, "Amortized efficiency of list update and paging rules", Communication of the ACM, 28:202--208, 1985.
List of Topics
indistinguishability
valency arguments
simulations
covering arguments
decidability
characterizations
topological arguments
List of References
Faith Fich and Eric Ruppert, "Lower Bounds in Distributed Computing", to appear in the proceedings of DISC 2000.
Nancy Lynch, "A Hundred Imppossibility Proofs for Distributed Computing", Proceedings of 8th PODC, 1989, pages 1-27.
H. Attiya and J. Welch, Distributed Computing: Fundamentals, Simulations, and Advanced Topics, McGraw Hill, 1998.
N. Lynch, Distributed Algorithms, Morgan-Kaufmann, 1996.
Kamal Jain, "A factor 2 approximation algorithm for the generalized steiner network problem", FOCS 98.
Uri Feige, "Approximating the Bandwidth via volume respecting embeddings", Journal of Computer and System Sciences, 60(3) pp 510-539.
Uri Feige and Robert Krauthgamer, "A polylogarithmic approximation of the minimum bisection", FOCS 00.
Uri Feige and Christian Scheideler, "Improved bounds for acyclic job-shop scheduling", STOC 98.
F. Chudak and D. Williamson, "Improved approximation algorithms for capacitated facility location problems", IPCO 98.
Dimitris Fotakis , Grammati Pantziou , George Pentaris and Paul Spirakis, "Frequency assignment in mobile and radio networks",DIMACS series on Dicrete Math and Theoretical Computer Science 45, Networks in Distributed Computing, AMS, 1999.
Dimitris Fotakis and Paul Spirakis,"A hamiltonian approach to the assignment of non - reusable frequencies",18th FST-TCS, 1998 , pp 18-29 , Springer Verlag ,
Grammati Pantziou, George Pentaris and Paul Spirakis, "Competitive call control in mobile networks",ISAAC, 1997 , Springer Verlag.
Dimitris Fotakis, Sotiris Nikoletseas, Vicky Papadopoulou and Paul Spirakis, "Hardness results and efficient approximations for radiocoloring in Planar Graphs",MFCS, 2000 , Springer - Verlag.
Hadzigiannakis , Sotiris Nikoletseas and Paul Spirakis, "Fundamental Control Algorithms in ad hoc mobile networks",SPAA, 1999.
Hadzigiannakis , Sotiris Nikoletseas and Paul Spirakis, "New Routing protocols for ad hoc mobile networks",to appear.
Agnarsson and Haldorsson, "Coloring powers of planar graphs",SODA, 2000.
Bertossi and Bonucceli,"Code assignement for hidden terminal interference avoidance in multihop packet radio networks", IEEE/ ACM Trans. Networking, 3,4 Aug 1995.
Prakash et al,"Distributed Dynamic Channel Allocation for Mobile Computing" , ACM PODC, 1995.
More information, if needed, can be obtained via e-mail at <adfocs00@mpi-sb.mpg.de>.