e-mail: mavronic@ucy.ac.cy

   http://www2.cs.ucy.ac.cy/~mavronic/
Books Research Articles Back to Main Page

 

See also my list of publications as they appear in DBLP.

Here is a pdf with all my publications.

See also my citations as they appear in Google Scholar.

>> Here is a Citations Catalogue I have compiled myself.

Please email me if you would like a copy of a publication that is not available electronically

© Copyright Notice:

The documents distributed by this server 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.

I include links to on-line papers and software, when appropriate, to ensure timely dissemination on a noncommercial basis. Technical reports are most likely to be available on-line. 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 the copyrights. These works may not be reposted without the explicit permission of the copyright holder.

  Books 

 

 

Thesis

 

 

(TH1) M. Mavronicolas, "Timing-Based, Distributed Computation: Algorithms and Impossibility Results", Ph.D. Thesis in Computer Science, Division of Applied Sciences, Harvard University, Cambridge, Massachusetts, July 1992.

 

 

To top of page 

 

Textbooks

 

 

Appeared

 

 

(T2) M. Mavronicolas, "Distributed Systems", Greek Open University, September 2005. ISBN: 960-538-574-0 (167 pages).

 

(T1) M. Mavronicolas, "Graph Theory", Greek Open University, December 2002. ISBN: 960-538-461-2 (314 pages). 

 

I have been receiving numerous personal letters from students of the Greek Open University, congratulating me for my two Distant-Learning textbooks they have been using and encouraging my to consider writing more textbooks for Greek Open University. Here is such a recent letter.

 

 

To top of page 

 

In Preparation (No Contract Yet)

 

 

(IPT2) M. Mavronicolas, "Theory of Computation", in preparation, December 2005. (588 pages, in Greek).  

 

(IPT1) M. Mavronicolas, "Distributed Computing with Shared Memory", in preparation, December 2005. (277 pages, in Greek).  

 

Note: These two textbooks resulted from my lecture notes for the classes CS211 and CS432 that I have been teaching. They have not reached yet their final form. They are expected to be completed in Spring 2006. They are available here, but they are password-protected. If you are interested, please email me to ask for the password(s).

 

 

To top of page 

 

Research Monographs

 

 

In Preparation (Contract Signed and Publication Date Scheduled)

 

 

(RM2) M. Mavronicolas and P. Spirakis, "Algorithmic Game Theory", Springer-Verlag, Spring 2007, to appear.

(If you are interested in using this book for a class you are teaching, please e-mail me and I will send you the current draft)

 

(RM1) C. Busch and M. Mavronicolas, "Counting Networks", Springer-Verlag, December 2006, to appear.

(If you are interested in using this book for a class you are teaching, please e-mail me and I will send you the current draft )

 

 

To top of page 

 

Edited Volumes

 

 

(EV3) P. Spirakis, M. Mavronicolas and S. Kontogiannis eds., "Internet and Network Economics", Proceedings of the 2nd International Workshop on Internet and Network Economics, Volume 4286, Lecture Notes in Computer Science, December 2006. ISBN 3-540-68138-8 (401 pages).

 

(EV2) M. Mavronicolas, M. Merritt and N. Shavit eds., "Networks in Distributed Computing", DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 45, American Mathematical Society, November 1998. ISBN 0-8218-0992-X (179 pages).

 

(EV1) M. Mavronicolas and Ph. Tsigas eds., "Distributed Algorithms", Proceedings of the 11th International Workshop on Distributed Algorithms, Lecture Notes in Computer Science, Vol. 1320, Springer-Verlag, Saarbrücken, Germany, September 1997. ISBN 3-540-63575-0 (333 pages).

 

 

To top of page 

 

Journal Special Issues

 

 

(SI3) S. Abramsky and M. Mavronicolas, guest editors, "Game Theory Meets Theoretical Computer Science", Special Issue, Theoretical Computer Science (Tracks A & B), Vol. 343, Nos. 1-2, October 2005. (282 pages)

 

(SI2) M. Mavronicolas, guest editor, "Algorithmic Issues in Communication Networks", Special Issue, Computing and Informatics (formerly Computers and Artificial Intelligence), Vol. 20, No. 2, March 2001. (132 pages)

 

(SI1) M. Mavronicolas, guest editor, "Distributed Algorithms", Special Issue, Theoretical Computer Science (Track A), Vol. 220, No. 1, June 1999. (319 pages)

 

To top of page 

Dictionaries

 

 

In Preparation (No Contract Yet)

 

 

(IPD1) M. Mavronicolas, "The Millenium Dictionary: English-Greek Dictionary of Theoretical Computer Science and Discrete Mathematics", in preparation, December 2005. (92 pages, in Greek).

 

 

To top of page 

 

  Research Articles 

 

 

Book Chapters

 

 

(BC3) M. Mavronicolas, V. Papadopoulou and P. Spirakis, "Algorithmic Game Theory and Applications", in Handbook of Applied Algorithms: Solving Scientific, Engineering, and Practical Problems, A. Nayak and I. Stojmenovic eds., John Wiley and Sons, pp. 287-316, March 2008.

 

(BC2) C. Busch, N. Demetriou, M. Herlihy and M. Mavronicolas, "A Combinatorial Characterization of Properties Preserved by Antitokens", Current Trends in Theoretical Computer Science, Vol. I: Algorithms And Complexity, G. Paun, G. Rozenberg and A. Salomaa eds., pp. 297-314, World Scientific Publishing, 2004.

 

(BC1) M. Mavronicolas, "Stability in Routing: Networks and Protocols" Current Trends in Theoretical Computer Science, Vol. I: Algorithms And Complexity, G. Paun, G. Rozenberg and A. Salomaa eds., pp. 435-450, World Scientific Publishing, 2004.

 

 

To top of page 

 

Journals

 

 

Appeared/Accepted

        (Partial List)

 

(J43) M. Mavronicolas and T. Sauerwald, "The Impact of Randomization in Smoothing Networks", Distributed Computing, Special Issue with selected papers from the 27th Annual ACM Symposium on Principles of Distributed Computing (PODC 2008), (Toronto, Canada, August 2008), March 2009, accepted.

 

(J42) R. Feldmann, M. Mavronicolas and A. Pieris, "Facets of the Fully Mixed Nash Equilibrium Conjecture", Theory of Computing Systems, Special Issue with selected papers from the 1st International Symposium on Algorithmic Game Theory (SAGT 2008), (Paderborn, Germany, April/May 2008), B. Monien and U.– P. Schroeder eds., March 2009, accepted.

 

(J41) M. Gairing, T. Lucking, M. Mavronicolas and B. Monien, "Computing Nash Equilibria for Scheduling on Restricted Parallel Links", Theory of Computing Systems, January 2009, accepted.

 

(J40) M. Mavronicolas and L. Michael, "A Substitution Theorem for Graceful Trees and its Applications", Discrete Mathematics, December 2008, accepted.

 

(J39) M. Gairing, T. Lucking, M. Mavronicolas, B. Monien and M. Rode, "Nash Equilibria in Discrete Routing Games with Convex Latency Functions", Journal of Computer and System Sciences, Vol. 74, No. 7, pp. 1199--1225, November 2008.

 

(J38) M. Mavronicolas, V. Papadopoulou, A. Philippou and P. Spirakis, "A Graph-Theoretic Network Security Game", International Journal of Autonomous and Adaptive Communications Systems, Special Issue on "Algorithmic Game Theory", R. Kannan and C. Busch, eds., Vol. 1, No. 4 pp. 390 -- 410, 2008.

 

(J37) M. Mavronicolas, M. Merritt and G. Taubenfeld, "Sequentially Consistent versus Linearizable Counting Networks", Distributed Computing, Vol. 21, No. 4,  pp. 249-269, October 2008. 

 

(J36) M. Mavronicolas, L. Michael and P. Spirakis, "Computing on a Partially Eponymous Ring", Theoretical Computer Science, Special Issue with selected papers from the 10th International Conference On Principles Of Distributed Systems (OPODIS 2006), (Bordeaux & Saint-Emilion, France, December 2006), A. A. Shvartsman guest ed.,  Vol. 410, No. 6-7, pp. 595--613, February 2009.

 

(J35) D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronicolas and P. Spirakis, "The Structure and Complexity of Nash Equilibria for a Selfish Routing Game" Theoretical Computer Science, Vol. 343, No. 1-2, pp. 133--157, October 2005 .

 

(J34) C. Busch, M. Magdon-Ismail and M. Mavronicolas, "Efficient Bufferless Packet Switching on Trees and Leveled Networks", Journal of Parallel and Distributed Computing, Vol. 67, No. 11, pp. 1168--1186, November 2007.  

 

(J33) D. Koukopoulos, M. Mavronicolas and P. Spirakis, "The Increase of the Instability of Networks due to Quasi-Static Link Capacities" Theoretical Computer Science, Vol. 381, No. 1-3, pp. 44--56, August 2007.  

 

(J32) C. Busch, M. Magdon-Ismail and M. Mavronicolas, "Universal Bufferless Packet Switching" SIAM Journal on Computing, Vol. 37, No. 4, pp. 1139-1162, 2007.  

 

(J31) D. Koukopoulos, M. Mavronicolas and P. Spirakis, "Performance and Stability Bounds for Dynamic Networks", Journal of Parallel and Distributed Computing, Vol. 67, No. 4, pp. 386-399, April 2007.

 

(J30) M. Mavronicolas, V. Papadopoulou, A. Philippou and P. Spirakis, "A Network Game with Attackers and a Defender", Algorithmica, Special Issue with selected papers from the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005) (Hainan, China, December 2005), X. Deng and D. Du guest eds., Vol. 51, No. 3, pp. 315-341, July 2008. 

 

(J29) M. Mavronicolas, P. Panagopoulou and P. Spirakis, "Cost Sharing Mechanisms for Fair Pricing of Resource Usage", Algorithmica, Special Issue with selected papers from the 1st International Workshop on Internet and Network Economics (WINE 2005) (Hong Kong, China, December 2005), X. Deng and Y. Ye guest eds., Vol. 52, No. 1, pp. 19--43, September 2008.

 

(J28) M. Gairing, T. Lucking, M. Mavronicolas and B. Monien, "The Price of Anarchy for Polynomial Social Cost", Theoretical Computer Science, Vol. 369, No. 1-3, pp. 116-135, December 2006.

 

(J27) T. Lucking, M. Mavronicolas, B. Monien and M. Rode, "A New Model for Selfish Routing", Theoretical Computer Science, Special Issue on Algorithmic Aspects of Global Computing, Ch. Kaklamanis guest ed., Vol. 406, No 3,pp.187--206, October 2008
.  

(J26) C. Busch, M. Magdon-Ismail, M. Mavronicolas and P. Spirakis, "Direct Routing: Algorithms and Complexity", Algorithmica, Special Issue with selected papers from the 12th Annual European Symposium on Algorithms (ESA 2004) (Bergen, Norway, September 2004), S. Albers and T. Radzik guest eds., Vol. 45, No. 1, pp. 45-68, June 2006. 

 

(J25) M. Gairing, T. Lucking, M. Mavronicolas and B. Monien, "The Price of Anarchy for Restricted Parallel Links", Parallel Processing Letters, Vol. 16, No. 1, pp. 117-132, March 2006. 

 

(J24) M. Mavronicolas and P. Spirakis, "The Price of Selfish Routing", Algorithmica, Vol. 48, No. 1, pp. 91-126, June 2007.

 

(J23) M. Gairing, T. Lucking, M. Mavronicolas, B. Monien and P. Spirakis, "Structure and Complexity of Extreme Nash Equilibria", Theoretical Computer Science (Special Issue titled "Game Theory Meets Theoretical Computer Science", M. Mavronicolas and S. Abramsky guest eds.), Vol. 343, Nos. 1-2, pp. 133-157, October 2005.

 

(J22) D. Koukopoulos, M. Mavronicolas, S. Nikoletseas and P. Spirakis, "The Impact of Network Structure on the Stability of Greedy Protocols", Theory of Computing Systems, Special Issue with selected papers from the 5th Italian Conference on Algorithms and Complexity (CIAC 2003) (Rome, Italy, May 2003), G. Persiano guest ed., Vol. 39, No. 4, pp. 425-460, July 2005.

 

(J21) P. Fatourou, M. Mavronicolas and P. Spirakis, "Efficiency of Oblivious versus Nonoblivious Schedulers for Optimistic, Rate-Based Flow Control", SIAM Journal on Computing, Vol. 34, No. 5, pp. 1216-1252, July 2005.

 

(J20) P. Fatourou, M. Mavronicolas and P. Spirakis, "Max-Min Fair Flow Control Sensitive to Priorities", Journal of Interconnection Networks, Vol. 6, No. 2, pp. 85-114, June 2005.

 

(J19) C. Busch, M. Mavronicolas and P. Spirakis, "The Cost of Concurrent, Low-Contention Read-Modify-Write", Theoretical Computer Science, Special Issue with selected papers from the 10th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2003) (Umea, Sweden, June 2003), J. F. Sibeyn and D. Peleg guest eds., Vol. 333, No. 3, pp. 373-400, March 2005.

 

(J18) C. Busch, M. Mavronicolas and P. Spirakis, "An Application of the Monotone Linearizability Lemma", Bulletin of the European Association for Theoretical Computer Science, No. 85, pp. 70-80, February 2005.

 

(J17) I. Chatzigiannakis, T. Dimitriou, M. Mavronicolas, S. Nikoletseas and P. Spirakis, "A Comparative Study of Protocols for Efficient Data Propagation in Smart Dust Networks", Parallel Processing Letters, Special Issue with selected papers from the 9th European Conference on Parallel Processing (Euro-Par 2003), (Klagenfurt, Austria, August 2003), H. Kosch, L. Boszormenyi and H. Hellwagner guest eds., Vol. 13, No. 4 pp. 615-627, November 2003.

 

(J16) E. Koutsoupias, M. Mavronicolas and P. Spirakis, "Approximate Equilibria and Ball Fusion", Theory of Computing Systems, Special Issue with selected papers from 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2002) (Andros, Greece, June 2002), Ch. Kaklamanis and L. M. Kirousis guests eds., Vol. 36, No. 6, pp. 683-693, November 2003.

 

(J15) M. Mavronicolas and N. Papadakis, "Trade-off Results for Connection Management", Theoretical Computer Science, Vol. 290, No. 1, pp.1-57, January 2003.

 

(J14) C. Busch, N. Demetriou, M. Herlihy and M. Mavronicolas, "Threshold Counters with Increments and Decrements", Theoretical Computer Science, Vol. 270, Nos. 1 & 2, pp. 811-826, January 2002.

 

(J13) M. Mavronicolas, "Stability in Routing: Networks and Protocols", Bulletin of the European Association for Theoretical Computer Science, No. 74, pp. 119-133, June 2001.

 

(J12) M. Mavronicolas, "Distributed Computing Theory To Date", Bulletin of the European Association for Theoretical Computer Science, No. 73, pp. 99-106, February 2001.

 

(J11) W. Aiello, C. Busch, M. Herlihy, M. Mavronicolas, N. Shavit and D. Touitou, "Supporting Increment and Decrement Operations in Balancing Networks", Chicago Journal of Theoretical   Computer Science, 2002-4, December 14, 2000 (electronic).

 

(J10) C. Busch, N. Demetriou, M. Herlihy and M. Mavronicolas, "A Combinatorial Characterization of Properties Preserved by Antitokens", Bulletin of the European Association for Theoretical Computer Science,, Number 71, pp. 114-132, June 2000.

 

(J9) M. Mavronicolas and D. Roth, "Linearizable Read/Write Objects", Theoretical Computer Science, Vol. 220, No. 1, pp. 267-319, June 1999.

 

(J8) M. Mavronicolas, "Timing-Based Connection Management", in M. Mavronicolas, M. Merritt and N. Shavit, eds., "Networks in Distributed Computing", DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 45, pp. 113-134, American Mathematical Society, October 1998. (In memory of late Professor Paris C. Kanellakis.)

 

(J7) M. Mavronicolas, "A q-Analog of Approximate Inclusion-Exclusion", Advances in Applied Mathematics, Vol. 20, No. 1, pp. 108-129, January 1998.

 

(J6) C. Busch and M. Mavronicolas, "Impossibility Results for Weak Threshold Networks", Information Processing Letters, Vol. 63, No. 2, pp. 125-157, March 1997.

 

(J5) M. Mavronicolas, "Balancing Networks: State-of-the-Art", Information Sciences: An International Journal, invited paper in Special Issue on Load Balancing, C. Nikolaou and L. Richter eds., Vol. 97, No. 1/2, pp. 125-157, March 1997.

 

(J4) C. Busch and M. Mavronicolas, "A Combinatorial Treatment of Balancing Networks", Journal of the ACM, Vol. 43, No. 5, pp. 794-839, September 1996.

 

(J3) C. Busch and M. Mavronicolas, "Proving Correctness for Balancing Networks", in P. M. Pardalos, K. G. Ramakrishnan and M. G. C. Resende eds., "Parallel Processing of Discrete Optimization Problems", DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 22, pp. 1-32, American Mathematical Society, July 1995.

 

(J2) H. Attiya and M. Mavronicolas, "Efficiency of Semi-Synchronous versus Asynchronous Networks", Mathematical Systems Theory (currently Theory of Computing Systems), Vol. 27, No. 6, pp. 547-571, November/December 1994.

 

(J1) M. Mavronicolas, "Efficiency of Semi-Synchronous versus Asynchronous Systems: Atomic Shared Memory", Computers and Mathematics with Applications, Vol. 25, No. 2, pp. 81-91, January 1993.

 

 

To top of page

   

Submitted by Invitation to Special Issues

 

 

 

 

To top of page 

 

Submissions

 

(JS4) M. Mavronicolas, B. Monien and V. Papadopoulou, "How Many Attackers Can Selfish Defenders Catch?" submitted to Discrete Applied Mathematics, November 2008.

 

(JS3) C. Busch and M. Mavronicolas, "An Efficient Counting Network", submitted to Theoretical Computer Science.

  

(JS1) M. Mavronicolas, "A Bound on the Rounds to Reach Lattice Agreement", submitted to Information Processing Letters.

 

 

To top of page 

 

Conference Proceedings (Refereed)

 

 

Extended Abstracts

 

 

(C58) R. Feldmann, M. Mavronicolas and B. Monien, "Nash Equilibria for Voronoi Games on Transitive Graphs", Proceedings of the 5th International Workshop on Internet and Network Economics  (WINE 2009), , Lecture Notes in Computer Science, Springer-Verlag, S. Leonardi ed., Rome, Italy, December 2009,  to appear .

 

(C57) M. Mavronicolas and T. Sauerwald "A Randomized, O(log w)-Depth 2-Smoothing Network", Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2009), Calgary, Canada, August 2009, to appear .

 

(C56) M. Mavronicolas, B. Monien, V. Papadopoulou and  F. Schoppmann, "Voronoi Games on Cycle Graphs", Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008), eds., pp. 503--514, Vol. 5162, Lecture Notes in Computer Science, Springer-Verlag, Ed. Ochmanski and J. Tyszkiewicz eds., Toruń, Poland, August 2008.

 

(C55) M. Mavronicolas and T. Sauerwald, "The Impact of Randomization in Smoothing Networks", Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing (PODC 2008), R. Bazzi, B. Patt-Shamir eds., pp. 345--354, Toronto, Canada, August 2008.

 

(C54) R. Feldmann, M. Mavronicolas and A. Pieris, "Facets of the Fully Mixed Nash Equilibrium Conjecture", Proceedings of the 1st International Symposium on Algorithmic Game Theory (SAGT 2008), B. Monien and U. P. Schroeder eds., pp. 145-157, Vol. 4997, Lecture Notes in Computer Science, Springer-Verlag, Paderborn, Germany, April/May 2008.

Slide show presentation available (pdf).

 

(C53) M. Mavronicolas, B. Monien and V. Papadopoulou, "How Many Attackers Can Selfish Defenders Catch?", CD-ROM Proceedings of the 41st Hawaii International Conference on System Sciences (JHICSS-41), Track on Software Technology, Minitrack on Algorithmic Challenges in Emerging Applications of Computing, Big Island, Hawaii, January 2008.

 

(C52) M. Mavronicolas, B. Monien and K. Wagner, "Weighted Boolean Formula Games", Proceedings of the 3rd International Workshop on Internet and Network Economics (WINE 2007), X. Deng and F. C. Graham eds., pp. 469-481, Vol. 4858, Lecture Notes in Computer Science, Springer-Verlag, San Diego, USA, December 2007.

 

(C51) M. Mavronicolas, I. Milchtaich, B. Monien and K. Tiemann, "Congestion Games with Player-Specific Constants", Proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2007), L. Kucera and A. Kucera eds., pp. 633-644, Vol. 4708, Lecture Notes in Computer Science, Springer-Verlag, Českı Krumlov, Czech Republic, August 2007.

 

(C50) M. Mavronicolas, L. Michael and P. Spirakis, "Computing on a Partially Eponymous Ring", Proceedings of the 10th International Conference On Principles Of Distributed Systems (OPODIS 2006), A. A. Shvartsman ed., pp. 380-394, Vol. 4305, Lecture Notes in Computer Science, Springer-Verlag, Bordeaux & Saint-Emilion, France, December 2006.

 

(C49) M. Mavronicolas, V. Papadopoulou, G. Persiano, A. Philippou and P. Spirakis, "The Price of Defense and Fractional Matchings", Proceedings of the 8th International Conference on Distributed Computing and Networking (ICDCN 2006), S. Chaudhuri, S. R. Das, H. Sekhar  and S. Tirthapura eds., pp. 115-126, Vol. 4308, Lecture Notes in Computer Science, Springer-Verlag, Guwahati, India, December 2006.

 

(C48) M. Mavronicolas, V. Papadopoulou, A. Philippou and P. Spirakis, "A Network Game with Attackers and a  Defender: A Survey", CD-ROM Proceedings of the 2nd European Conference on Complex Systems 2006 (ECCS 2006), Oxford, Great Britain, September 2006. 

 

(C47) M. Mavronicolas, L. Michael, V. Papadopoulou, A. Philippou and P. Spirakis, "The Price of Defense", Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006), R. Kralovic and P. Urzyczyn eds., pp. 717-728, Vol. 4162, Lecture Notes in Computer Science, Springer-Verlag, Bratislava, Slovakia, August/September 2006.

Slide show presentation available (ppt) (pdf).

 

(C46) M. Gelastou, M. Mavronicolas, V. Papadopoulou, A. Philippou and P. Spirakis, "The Power of the Defender", CD-ROM Proceedings of the 2nd International Workshop on Incentive-Based Computing (IBC 2006), in conjunction with the 26th IEEE International Conference on Distributed Computing (ICDCS 2006), Lisboa, Portugal, July 2006. (6 pages)

Slide show presentation available (ppt) (pdf)

 

(C45) M. Mavronicolas, V. Papadopoulou, A. Philippou and P. Spirakis, "A Network Game with Attacker and Protector Entities", Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005), X. Deng and D. Du eds., pp. 288-297, Vol. 3827, Lecture Notes in Computer Science, Springer-Verlag, Hainan, China, December 2005.

Slide show presentation available (ppt) (pdf)

 

(C44) R. Elsasser, M. Gairing, T. Lucking, M. Mavronicolas and B. Monien, "A Simple Graph-Theoretic Model for Selfish Restricted Scheduling", Proceedings of the 1st International Workshop on Internet and Network Economics (WINE 2005), X. Deng and Y. Ye eds., pp. 195-209, Vol. 3828, Lecture Notes in Computer Science, Springer-Verlag, Hong Kong, China, December 2005.

Slide show presentation available (pdf)

 

(C43) M. Mavronicolas, P. Panagopoulou and P. Spirakis, "A Cost Mechanism for Fair Pricing of Resource Usage", Proceedings of the 1st International Workshop on Internet and Network Economics (WINE 2005), X. Deng and Y. Ye eds., pp. 210-224, Vol. 3828, Lecture Notes in Computer Science, Springer-Verlag, Hong Kong, China, December 2005.

Slide show presentation available (pdf)

 

(C42) M. Mavronicolas, V. Papadopoulou, A. Philippou and P. Spirakis, "A Graph-Theoretic Network Security Game", Proceedings of the 1st International Workshop on Internet and Network Economics (WINE 2005), X. Deng and Y. Ye eds., pp. 969-978, Vol. 3828, Lecture Notes in Computer Science, Springer-Verlag, Hong Kong, China, December 2005.

Slide show presentation available (ppt) (pdf)

 

(C41) C. Busch, M. Mavronicolas and P. Spirakis, "Monotone Operations and Monotone Groups", Proceedings of the 1st International Conference on Algebraic Informatics 2005, S. Bozapalidis, A. Kalampakas and G. Rahonis eds., pp. 175-195, Aristotle University of Thessaloniki, Thessaloniki, Greece, October 2005.

 

 

(C40) C. Busch, M. Magdon-Ismail and M. Mavronicolas, "Universal Bufferless Routing", Proceedings of the 2nd Workshop on Approximation and Online Algorithms (WAOA 2004), G. Persiano and R. Solis-Oba eds., pp. 239-252, Vol. 3351,  Lecture Notes in Computer Science, Springer-Verlag, Bergen, Norway, September 2004.

Slideshow presentation available (ppt) (pdf)

 

(C39) C. Busch, M. Magdon-Ismail, M. Mavronicolas and P. Spirakis, "Direct Routing: Algorithms and Complexity", Proceedings of the 12th Annual European Symposium on Algorithms (ESA 2004), S. Albers and T. Radzik eds., pp. 134-145, Vol. 3221, Lecture Notes in Computer Science, Springer-Verlag, Bergen, Norway, September 2004.

 

(C38) M. Gairing, T. Lucking, M. Mavronicolas and B. Monien, "The Price of Anarchy for Polynomial Social Cost", Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), J. Fiala, V. Koubek and J. Kratochvil eds., pp. 574-585, Vol. 3153, Lecture Notes in Computer Science, Springer-Verlag, Prague, Czech Republic, August 2004.

 

(C37) C. Busch, M. Magdon-Ismail, M. Mavronicolas and R. Wattenhofer, "Near-Optimal Hot-Potato Routing on Trees", Proceedings of the 10th European Conference on Parallel Processing (Euro-Par 2004), M. Danelutto, M. Vanneschi and D. Laforenza eds., pp. 820-827, Vol. 3149, Lecture Notes in Computer Science, Springer-Verlag, Pisa, Italy, August/September 2004.

 

(C36) M. Gairing, T. Lucking, M. Mavronicolas, B. Monien and M. Rode, "Nash Equilibria in Discrete Routing Games with Convex Latency Functions", Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2004), J. Diaz, J. Karhumaki, A. Lepisto, D. Sanella eds., pp. 645-657, Vol. 3142, Lecture Notes in Computer Science, Springer-Verlag, Turku, Finland, July 2004.

 

(C35) M. Gairing, T. Lucking, M. Mavronicolas and B. Monien, "Computing Nash Equilibria for Scheduling on Restricted Parallel Links", Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC 2004), pp. 613-622, June 2004.

 

(C34) D. Koukopoulos, M. Mavronicolas and P. Spirakis, "Performance and Stability Bounds for Dynamic Networks", Proceedings of the 7th International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN 2004), pp. 239-246, Hong Kong, SAR, China, May 2004.

 

(C33) T. Lucking, M. Mavronicolas, B. Monien and M. Rode, "A New Model for Selfish Routing", Proceedings of the 21st International Symposium on Theoretical Aspects Of Computer Science (STACS 2004), V. Diekert and M. Habib eds., pp. 547-558, Vol. 2996, Lecture Notes in Computer Science, Springer-Verlag, Montpellier, France, March 2004.

 

(C32) M. Gairing, T. Lucking, M. Mavronicolas, B. Monien and P. Spirakis, "Extreme Nash Equilibria", Proceedings of the 8th Italian Conference on Theoretical Computer Science (ICTCS 2003), C. Blundo and C. Laneve eds., pp. 1-20, Vol. 2841, Lecture Notes in Computer Science, Springer-Verlag, Bertinoro, Italy, October 2003.

 

(C31) I. Chatzigiannakis, T. Dimitriou, M. Mavronicolas, S. Nikoletseas and P. Spirakis, "A Comparative Study of Protocols for Efficient Data Propagation in Smart Dust Networks", Proceedings of the 9th European Conference on Parallel Processing (Euro-Par 2003), H. Kosch, L. Boszormenyi and H. Hellwagner eds., pp. 1003-1016, Vol. 2790, Lecture Notes in Computer Science, Springer-Verlag, Klagenfurt, Austria, August 2003. (Note: Accepted as distinguished paper).

 

(C30) T. Lucking, M. Mavronicolas, B. Monien, M. Rode, P. Spirakis and I. Vrto, "Which is the Worst-Case Nash Equilibrium?", Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS 2003), B. Rovan and P. Vojtas eds., pp. 551-561, Vol. 2747, Lecture Notes in Computer Science, Springer-Verlag, Bratislava, Slovak Republic, August 2003.

 

(C29) D. Koukopoulos, M. Mavronicolas and P. Spirakis, "Instability of Networks with Quasi-Static Link Capacities", Proceedings of the 10th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2003), J. F. Sibeyn ed., pp. 179-194, Proceedings in Informatics 17, Carleton Scientific, Umeå, Sweden, June 2003.

 

(C28) C. Busch, M. Mavronicolas and P. Spirakis, "The Cost of Concurrent, Low-Contention Read-Modify-Write", Proceedings of the 10th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2003), J. F. Sibeyn ed., pp. 57-72, Proceedings in Informatics 17, Carleton Scientific, Umeå, Sweden, June 2003.

 

(C27) D. Koukopoulos, M. Mavronicolas, S. Nikoletseas and P. Spirakis, "The Impact of Network Structure on the Stability of Greedy Protocols", Proceedings of the 5th Italian Conference on Algorithms and Complexity (CIAC 2003), R. Petreschi, G. Persiano and R. Silvestri eds., pp. 251-263, Vol. 2653, Lecture Notes in Computer Science, Springer-Verlag, Rome, Italy, May 2003.

 

(C26) D. Koukopoulos, M. Mavronicolas, S. Nikoletseas and P. Spirakis, "On the Stability of Compositions of Universally Stable, Greedy Contention-Resolution Protocols", Proceedings of the 16th International Symposium on DIStibuted Computing (DISC 2002), (formerly International Workshop on Distributed Algorithms), D. Malkhi ed., pp. 88-102, Vol. 2508, Lecture Notes in Computer Science, Springer-Verlag, Toulouse, France, October 2002.

 

(C25) E. Koutsoupias, M. Mavronicolas and P. Spirakis, "Approximate Equilibria and Ball Fusion", Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2002), Ch. Kaklamanis and  L. M. Kirousis eds., pp. 223-235, Proceedings in Informatics 13, Carleton Scientific, Andros, Greece, June 2002.

 

(C24) D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronicolas and P. Spirakis, "The Structure and Complexity of Nash Equilibria for a Selfish Routing Game", Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP 2002), P. Widmayer, F. Triguero, R. Morales, M. Hennessy, S. Eidenbenz and R. Conejo eds., pp. 123-134, Vol. 2380, Lecture Notes in Computer Science, Springer-Verlag, Malaga, Spain, July 2002.

 

(C23) M. Mavronicolas, A. Mouskos and P. Spirakis, "The Cost of Lack of Coordination in Distributed Network Routing", Proceedings of the 2nd International Workshop on Approximation and Randomized Algorithms in Communication Networks (ARACNE 2001), Ch. Kaklamanis ed., pp. 65-84, Proceedings in Informatics 12, Carleton Scientific, Aarhus, Denmark, August 2001.

 

(C22) M. Mavronicolas and P. Spirakis, "The Price of Selfish Routing", Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC 2001), pp. 510-519, July 2001.

 

(C21) C. Busch, N. Demetriou, M. Herlihy and M. Mavronicolas, "A Combinatorial Characterization of Properties Preserved by Antitokens", Proceedings of the 6th European Conference on Parallel Processing (Euro-Par 2000). A. Bode, T. Ludwig, W. Karl and R. Wismüller eds., pp. 575-582, Vol. 1900, Lecture Notes in Computer Science, Springer-Verlag, Munich, Germany, August/September 2000.

 

(C20) M. Eleftheriou and M. Mavronicolas, "Linearizability in the Presence of Drifting Clocks and Under Different Delay Assumption", Proceedings of the 13th International Symposium on DIStributed Computing (DISC 1999), (formerly International Workshop on Distributed Algorithms), P. Jayanti ed., pp. 327-341, Vol. 1693, Lecture Notes in Computer Science, Springer-Verlag, Bratislava, Slovakia, September 1999.

 

(C19) S. Georgiades, M. Mavronicolas and P. Spirakis, "Optimal, Distributed Decision-Making: The Case of No Communication", Proceedings of the 12th International Symposium on Fundamentals of Computation Theory (FCT 1999), G. Ciobanu and G. Paun eds., pp. 293-303, Vol. 1684, Lecture Notes in Computer Science, Springer-Verlag, Iasi, Romania, August/September 1999.

 

(C18) C. Busch, N. Demetriou, M. Herlihy and M. Mavronicolas, "Threshold Counters with Increments and Decrements", Proceedings of the 6th International Colloquium on Structural Information and Communication Complexity (SIROCCO 1999), C. Gavoille, J. C. Bermond and A. Raspalid eds., pp. 47-61, Proceedings in Informatics 5, Carleton Scientific, Lacanau, France, June/July 1999.

 

(C17) M. Mavronicolas, M. Merritt and G. Taubenfeld, "Sequentially Consistent versus Linearizable Counting Networks", Proceedings of the 18th Annual ACM Symposium on Principles of Distributed Computing (PODC 1999), pp. 133-142, Atlanta, Georgia, May 1999.

 

(C16) W. Aiello, C. Busch, M. Herlihy, M. Mavronicolas, N. Shavit and D. Touitou, "Supporting Increment and Decrement Operations in Balancing Networks", Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science (STACS 1999), G. Meinel and S. Tison eds., pp. 377-386, Vol. 1563, Lecture Notes in Computer Science, Springer-Verlag, Trier, Germany, March 1999.

 

(C15) P. Fatourou, M. Mavronicolas and P. Spirakis, "Max-Min Fair Flow Control Sensitive to Priorities", Proceedings of the 2nd International Conference on Principles of Distributed Systems (OPODIS 1998), pp. 45-59, Hermes Science Publications 1999, Amiens, France, December 1998.

 

(C14) L. Hadjimitsis and M. Mavronicolas, "Contention in Balancing Networks Resolved", Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing (PODC 1998), pp. 41-50, Puerto Vallarta, Mexico, June/July 1998.

 

(C13) P. Fatourou, M. Mavronicolas and P. Spirakis, "The Global Efficiency of Distributed, Rate-Based, Flow Control Algorithms", Proceedings of the 5th International Colloquium on Structural Information and Communication Complexity (SIROCCO 1998), pp. 244-258, Amalfi, Italy, June 1998.

 

(C12) C. Busch and M. Mavronicolas, "An Efficient Counting Network", Proceedings of the 1st Merged Symposium IPPS/SPDP 1998 (12th International Parallel Processing Symposium & 9th IEEE Symposium on Parallel and Distributed Processing), pp. 380-384, Orlando, Florida, March/April 1998.

 

(C11) M. Mavronicolas and N. Papadakis, "Trade-off Results for Connection Management", Proceedings of the 11th International Symposium on Fundamentals of Computation Theory (FCT 1997), B. S. Chlebus and L. Csaja eds., pp. 340-351, Lecture Notes in Computer Science, Vol. 1279, Springer-Verlag, Krakow, Poland, September 1997.

 

(C10) P. Fatourou, M. Mavronicolas and P. Spirakis, "Efficiency of Oblivious versus Non-Oblivious Schedulers for Optimistic, Rate-Based Flow Control", Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing (PODC 1997), pp. 139-148, Santa Barbara, California, August 1997.

 

(C9) P. Fatourou, M. Mavronicolas and P. Spirakis, "Advances in Rate-Based Flow Control", Proceedings of the 4th International Colloquium on Structural Information and Communication Complexity (SIROCCO 1997), Carleton University Press, pp. 266-281, June 1997.

 

(C8) M. Mavronicolas, M. Papatriantafilou and Ph. Tsigas, "The Impact of Timing on Linearizability in Counting Networks", Proceedings of the 11th International Parallel Processing Symposium (IPPS 1997), pp. 684-688, Geneva, Switzerland, April 1997.

 

(C7) S. Kapidakis and M. Mavronicolas, "Distributed, Low Contention Task Allocation", Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing (SPDP 1996), pp. 358-365, New Orleans, Louisiana, October 1996.

 

(C6) C. Busch and M. Mavronicolas, "A Combinatorial Treatment of Balancing Networks", Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing (PODC 1994), pp. 206-215, Los Angeles, California, August 1994.

 

(C5) N. Hardavellas, D. Karakos and M. Mavronicolas, "Notes on Sorting and Counting Networks", Proceedings of the 7th International Workshop on Distributed Algorithms (WDAG 1993), A. Schiper, ed., pp.234-248, Lecture Notes in Computer Science, Vol. 725, Springer-Verlag, Lausanne, Switzerland, September 1993.

 

(C4) M. Mavronicolas, "An Upper and a Lower Bound for Tick Synchronization", Proceedings of the 13th IEEE Real-Time Systems Symposium (RTSS 1992), pp. 246-255, Phoenix, Arizona, December 1992.

 

(C3) M. Mavronicolas and D. Roth, "Efficient, Strongly Consistent Implementations of Shared Memory", Proceedings of the 6th International Workshop on Distributed Algorithms (WDAG 1992), A. Segall and S. Zaks eds., pp. 346-361, Lecture Notes in Computer Science, Vol. 486, Springer-Verlag, Haifa, Israel, November 1992.

 

(C2) M. Mavronicolas and D. Roth, "Sequential Consistency and Linearizability: Read/Write Objects", Proceedings of the 29th Annual Allerton Conference on Communication, Control and Computing (ALLERTON 1991), pp. 683-692, Allerton, Illinois, October 1991.

 

(C1) H. Attiya and M. Mavronicolas, "Efficiency of Semi-Synchronous versus Asynchronous Networks", Proceedings of the 28th Annual Allerton Conference on Communication, Control and Computing (ALLERTON 1990), pp. 578-587, Allerton, Illinois, October 1990.

 

     

To top of page 

 

Brief Announcements and Other

 

 

(BA11) M. Mavronicolas, P. Panagopoulou and P. Spirakis, "Cost Sharing Mechanisms for Fair Pricing of Resources Usage", Proceedings of the Dagstuhl Seminar on Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar Series 05361), September 2005.

 

(BA10) M. Gairing, T. Lucking, M. Mavronicolas and B. Monien, "The Price of Anarchy for Polynomial Social Cost", Proceedings of the Dagstuhl Seminar on Computing and Markets 2005 (Dagstuhl Seminar Series 05011), January 2005.

 

(BA9) M. Mavronicolas and P. Spirakis, "Optimal, Distributed Decision-Making: The Case of No Communication", Proceedings of the 18th Annual ACM Symposium on Principles of Distributed Computing (PODC 1999), p. 279, Atlanta, Georgia, May 1999.

 

(BA8) P. Fatourou, M. Mavronicolas and P. Spirakis, "The Global Efficiency of Distributed, Rate-Based, Flow Control Algorithms", Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing (PODC 1998), p. 311, Puerto Vallarta, Mexico, June/July 1998.

 

(BA7) M. Mavronicolas, "Wait-Free Solvability Via Combinatorial Topology", Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing (PODC 1996), p. 277, Philadelphia, Philadelphia, May 1996.

 

(BA6) C. Busch and M. Mavronicolas, "The Strength of Counting Networks", Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing (PODC 1996), p. 311, Philadelphia, Philadelphia, May 1996.

 

(BA5) C. Busch and M. Mavronicolas, "A Logarithmic Depth Counting Network", Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing (PODC 1995), p. 275, Ottawa, Canada, August 1995.

 

(BA4) S. Kapidakis and M. Mavronicolas, "Load Balancing Networks", Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing (PODC 1995), p. 276, Ottawa, Canada, August 1995.

 

(BA3) C. Busch, N. Hardavellas and M. Mavronicolas, "Contention in Counting Networks", Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing (PODC 1994), p. 404, Los Angeles, California, August 1994.

 

(BA2) M. Mavronicolas, "The Impact of Synchronization on the Session Problem", Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing (PODC 1994), p. 379, Los Angeles, California, August 1994.

 

(BA1) M. Mavronicolas, "A q-Analog of Approximate Inclusion-Exclusion", Proceedings of the 7th SIAM Conference on Discrete Mathematics, Albuquerque, New Mexico, June 1994.

     

 

To top of page 

 

Submissions

 

 

 

To top of page 

 

 

Technical Reports (Refereed)

 

 

(TR1) D. Koukopoulos, M. Mavronicolas and P. Spirakis, "FIFO is Unstable at Arbitrarily Low Rates (Even in Planar Networks)", Electronic Colloquium on Computational Complexity (ECCS) (ISSN 1433-8092), Technical Report TR03-016, accepted on April 8, 2003.

 

 

To top of page 

 

Unpublished (In Preparation)

 

 

 

To top of page