ISB-Tree: A New Indexing Scheme with Efficient Expected Behaviour. A.C. Kaporis, C. Makris, G. Mavritsakis, S. Sioutas, A. Tsakalidis, K. Tsichlas, C. Zaroliagis: Journal of Discrete Algorithms, Elsevier. Accepted.

Efficient Processing of 3-Sided Range Queries with Probabilistic Guarantees. A. Kaporis, S. Sioutas, K. Tsakalidis, K. Tsichlas, A. Papadopoulos. 13th International Conference on Database Theory  (ICDT 2010), March 22-26, Lausanne, Switzerland.

The Impact of Social Ignorance on Weighted Congestion Games. Dimitris Fotakis, Vasilis Gkatzelis, Alexis Kaporis and Paul Spirakis. Wine 2009, Rome.

Dynamic 3-sided Planar Range Queries with Expected Doubly Logarithmic Time. Gerth Stølting Brodal, Alexis C. Kaporis, Spyros Sioutas, Konstantinos Tsakalidis, and Kostas Tsichlas. 20th International Symposium on Algorithms and Computation (ISAAC 2009), December 16-18, 2009, Hawaii, USA.

Improved bounds for finger search on a RAM.  Alexis C. Kaporis, Christos Makris, Spyros Sioutas, Athanasios Tsakalidis, Kostas Tsichlas, Christos Zaroliagis. Algorithmica, to appear.

 

 

 

 

 

 

 

 

Efficient Methods for Selfish Network Design. D. Fotakis, A. C. Kaporis and P. Spirakis. 36th International Colloquium on  Automata, Languages and Programming  (ICALP 09). July 5 - 12, 2009, Rhodes - Greece

Atomic congestion games: fast, myopic and concurrent. D. Fotakis, A.C. Kaporis and P. Spirakis. Theory of Computing Systems (TOCS).

The price of Optimum in Stackelberg games on arbitrary networks and latency functions.  A. C. Kaporis and P. G. Spirakis. Theoretical Computer Science. To appear.

On the chromatic number of a random 5-regular graph. J. Diaz, A.C. Kaporis, G. Kemkes, L.M. Kirousis, X. Pérez, N.C. Wormald. Journal of Graph Theory, Wiley. To appear.

Myopic distributed protocols for singleton and independent-resource congestion games.  A.C. Kaporis, D. Kalles, P.G. Spirakis.  7th International Workshop on Experimental Algorithms (WEA '08) May 30 – June 2, 2008 Provincetown, Cape Cod, Massachusetts, USA. Some nice photos of J. Petit  and McGeoch.

Atomic congestion games: fast, myopic and concurrent. D. Fotakis, A.C. Kaporis and P. Spirakis.  1st International Symposium on Algorithmic Game Theory (SAGT '08). April 30 - May 2, 2008, Paderborn, Germany. Invited paper to a special issue to journal Theory of Computing Systems (TOCS), dedicated to the SAGT'08 best papers

Approximating almost all instances of Max­Cut within a ratio above the Hastad threshold. A.C. Kaporis, L.M. Kirousis, E.C. Stavropoulos
 14th Annual European Symposium on Algorithms (ESA 2006), 11-13 September 2006, ETH Zürich, Zürich, Switzerland. Here is the code  that on input a random graph of average degree d= O(1) computes the upper&lower bounds on the typical value of the cut.

 The price of Optimum in Stackelberg games on arbitrary networks and latency functions. A.C. Kaporis and P.G. Spirakis
18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2006), Cambridge, MA, USA, July 30 - August 2, 2006.

 Dynamic Interpolation Search Revisited. A. Kaporis, C. Makris, S. Sioutas, A. Tsakalidis, K. Tsichlas and C. Zaroliagis. 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006),  July 9 - 16, 2006 S. Servolo, Venice - Italy. 

 5-Regular Graphs are 3-Colorable with Uniformly Positive Probability.J. Diaz, G. Grammatikopoulos, A.C. Kaporis, L.M. Kirousis, X.
Perez, D.G.~Sotiropoulos, 13th Annual European Symposium on Algorithms (ESA '05), Spain, October 3-6, 2005. A program on C (to be updated shortly), with step 1/1000 it takes 10secs (1/5000 takes 20 hours) in a 3.4 cpu, (with explanatory notes) for checking the convexity of the logarithm of the second moment of the bichromate random varible: LPDMs  Also:  a matlab program that maximizes the second moment of the bichromate random varible: MAX Time: [step= 1/10, time= 39.8750 secs, global max= 58.14 < 58.23=barycenter]-[step= 1/20, time= 533.5000 secs, global max= 58.1486 < 58.23=barycenter]-[step= 1/30, time= 2.5255e+003 secs, global max= 58.1486 < 58.23=barycenter]

 The price of Optimum in Stackelberg games (to be updated)A. C. Kaporis, P. G. Spirakis,  Electronic Colloquium in Computational Complexity (ECCC' 05), Report No. 56 (2005), University of Trier. Also,  technical report in:  Dynamically Evolving, Large-Scale Information Systems (DELIS), supported by Future and Emerging Technologies programme of the EU under contract 001907.

 Partitioning networks into classes of mutually isolated nodesJ. Diaz, A.C. Kaporis, L.M. Kirousis, X. Perez, European Conference on Complex Systems (ECCS '05), Paris, 14-18 November 2005

 ISB-Tree: A New Indexing Scheme with Efficient Expected BehaviourA.C. Kaporis, C. Makris, G. Mavritsakis, S. Sioutas, A. Tsakalidis, K. Tsichlas, C. Zaroliagis, 16th Annual International Symposium on Algorithms and Computation (ISAAC '05), December 19 - 21, 2005, Sanya, Hainan, China.

 Experimental results for Stackelberg scheduling strategies.  A. C. Kaporis, L. M. Kirousis, E. I. Politopoulou, P. G. Spirakis, 4th International Workshop on Efficient and Experimental Algorithms (WEA '05), Springer Verlag, Lecture Notes
in Computer Science 3503, 77-89, Santorini Islands, Greece, 2005

 Improved bounds for finger search on a RAM.  Alexis C. Kaporis, Christos Makris, Spyros Sioutas, Athanasios Tsakalidis, Kostas Tsichlas, Christos Zaroliagis, 11th Annual European Symposium on Algorithms (ESA '03), Budapest, Hungary.

 How to prove conditional randomness using the principle of deferred decisions. A. C. Kaporis, L. Kirousis, Y. Stamatiou, Special Volume on Computational Complexity and Statistical Physics, Santa Fe Institute of Technology, Academic Press.

 The probabilistic analysis of a greedy satisfiability algorithm.   A. C. Kaporis, L. M. Kirousis, E. G. Lalas, Random Structures and Algorithms, Wiley.

 Lower bounds to the conjectured threshold value for the 3-SAT problem. A. C. Kaporis, L. M. Kirousis, E. G. Lalas,  4th Pan-Hellenic Logic Symposium (PLS '03), Thessaloniki, Greece

 Selecting complementary pairs of literals.  A. C. Kaporis, L. M. Kirousis, E. G. Lalas, Electronic Notes in Discrete Mathematics, Elsevier Science, 16 (2003)

 The probabilistic analysis of a greedy satisfiability algorithm.   Alexis C. Kaporis, Lefteris M. Kirousis, Efthimios G. Lalas, 10th Annual European Symposium on Algorithms (ESA '02) Rome, Italy. Lecture Notes in Computer Science, Springer-Verlag, Vol: 2461/2002, January 2002, pp. 574-585. Also in 5th International Symposium on the Theory and Applications of Satisfiability Testing (SAT '02), Cincinnati, USA. Also in journal: Random Structures and Algorithms, Wiley,  28(4), 444--480.

 The unsatisfiability threshold revisited. A. C. Kaporis, L. M. Kirousis, Y. C. Stamatiou Malvina Vamvakari and M. Zito, Discrete Applied Mathematics, Vol. 22, Issue 2, 1525--1538, Elsevier. A preliminary version appeared in: 16th Annual IEEE Symposium on Logic in Computer Science (LICS '01) affiliated Workshop on Theory and Applications of Satisfiability Testing (SAT '01), Boston, USA

 Coupon collectors, q-binomial coefficients and the unsatisfiability threshold. Alexis C. Kaporis, Lefteris M. Kirousis, Yannis C. Stamatiou, Malvina Vamvakari, and Michele Zito. ICTCS 01, LNCS 2202, pp. 328.

 A note on the non-colorability threshold of a random graph. Alexis C. Kaporis, Lefteris M. Kirousis, Yannis C. Stamatiou. Electronic Journal of Combinatorics, Volume 7(1) 2000 R 29

 Corrigendum to: ''A note on the non-colorability threshold of a random graph''.  Ioannis Giotis, Alexis C. Kaporis, Lefteris M. Kirousis. Electronic Journal of Combinatorics, Volume 7(1) 2000 R 29 Comments.

 Locating information with uncertainty in fully interconnected networks with applications to world wide web information retrieval. Alexis C. Kaporis, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou, and Elias C. Stavropoulos. Computer Journal, Volume 44, Issue 4, pp. 221-229.  

 

Last update: July 8 2008

Text Box: Book chapters and Reviews Reviewer at American Mathematical Society Mathematical Reviews database. Handbook on NP-Completeness: Theory and Applications (handbook editor:  T. Gonjalez, U. California, Santa Barbara) by Chapman & Hall/CRC in the Computer & Information Science Series (series editor: S. Sahni,  U. Florida).Contributed Chapter (in preparation): Selfish splittable flows and NP-completeness (Kaporis  Spirakis) The Encyclopedia of Algorithms will be a comprehensive set of solutions to important algorithmic problems for researchers interested in quickly locating useful information. The first edition of the reference will focus on high-impact solutions from the most recent decade; later editions will widen the scope of the work. Contributed lemmata:   Algorithms for the Price of Optimum in Stackelberg Games (2005; Kaporis, Spirakis)  Thresholds for random k-SAT (2002; Kaporis, Kirousis, Lalas) Computational Complexity and Statistical Physics: Contributed chapter: Proving conditional randomness using the principle of Deferred Decisions (Kaporis, Kirousis, Stamatiou Publications ISB-Tree: A New Indexing Scheme with Efficient Expected Behaviour. A.C. Kaporis, C. Makris, G. Mavritsakis, S. Sioutas, A. Tsakalidis, K. Tsichlas, C. Zaroliagis: Journal of Discrete Algorithms, Elsevier. Accepted. Efficient Processing of 3-Sided Range Queries with Probabilistic Guarantees. A. Kaporis, S. Sioutas, K. Tsakalidis, K. Tsichlas, A. Papadopoulos. 13th International Conference on Database Theory  (ICDT 2010), March 22-26, Lausanne, Switzerland. The Impact of Social Ignorance on Weighted Congestion Games. Dimitris Fotakis, Vasilis Gkatzelis, Alexis Kaporis and Paul Spirakis. Wine 2009, Rome. Dynamic 3-sided Planar Range Queries with Expected Doubly Logarithmic Time. Gerth Stølting Brodal, Alexis C. Kaporis, Spyros Sioutas, Konstantinos Tsakalidis, and Kostas Tsichlas. 20th International Symposium on Algorithms and Computation (ISAAC 2009), December 16-18, 2009, Hawaii, USA. Improved bounds for finger search on a RAM.  Alexis C. Kaporis, Christos Makris, Spyros Sioutas, Athanasios Tsakalidis, Kostas Tsichlas, Christos Zaroliagis. Algorithmica, to appear. Efficient Methods for Selfish Network Design. D. Fotakis, A. C. Kaporis and P. Spirakis. 36th International Colloquium on  Automata, Languages and Programming  (ICALP 09). July 5 - 12, 2009, Rhodes - Greece Atomic congestion games: fast, myopic and concurrent. D. Fotakis, A.C. Kaporis and P. Spirakis. Theory of Computing Systems (TOCS). The price of Optimum in Stackelberg games on arbitrary networks and latency functions.  A. C. Kaporis and P. G. Spirakis. Theoretical Computer Science. To appear. On the chromatic number of a random 5-regular graph. J. Diaz, A.C. Kaporis, G. Kemkes, L.M. Kirousis, X. Pérez, N.C. Wormald. Journal of Graph Theory, Wiley. To appear. Myopic distributed protocols for singleton and independent-resource congestion games.  A.C. Kaporis, D. Kalles, P.G. Spirakis.  7th International Workshop on Experimental Algorithms (WEA '08) May 30 – June 2, 2008 Provincetown, Cape Cod, Massachusetts, USA. Some nice photos of J. Petit  and McGeoch. Atomic congestion games: fast, myopic and concurrent. D. Fotakis, A.C. Kaporis and P. Spirakis.  1st International Symposium on Algorithmic Game Theory (SAGT '08). April 30 - May 2, 2008, Paderborn, Germany. Invited paper to a special issue to journal Theory of Computing Systems (TOCS), dedicated to the SAGT'08 best papers Approximating almost all instances of Max­Cut within a ratio above the Hastad threshold. A.C. Kaporis, L.M. Kirousis, E.C. Stavropoulos 14th Annual European Symposium on Algorithms (ESA 2006), 11-13 September 2006, ETH Zürich, Zürich, Switzerland. Here is the code  that on input a random graph of average degree d= O(1) computes the upper&lower bounds on the typical value of the cut.  The price of Optimum in Stackelberg games on arbitrary networks and latency functions. A.C. Kaporis and P.G. Spirakis 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2006), Cambridge, MA, USA, July 30 - August 2, 2006.  Dynamic Interpolation Search Revisited. A. Kaporis, C. Makris, S. Sioutas, A. Tsakalidis, K. Tsichlas and C. Zaroliagis. 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006),  July 9 - 16, 2006 S. Servolo, Venice - Italy.   5-Regular Graphs are 3-Colorable with Uniformly Positive Probability.J. Diaz, G. Grammatikopoulos, A.C. Kaporis, L.M. Kirousis, X. Perez, D.G.~Sotiropoulos, 13th Annual European Symposium on Algorithms (ESA '05), Spain, October 3-6, 2005. A program on C (to be updated shortly), with step 1/1000 it takes 10secs (1/5000 takes 20 hours) in a 3.4 cpu, (with explanatory notes) for checking the convexity of the logarithm of the second moment of the bichromate random varible: LPDMs  Also:  a matlab program that maximizes the second moment of the bichromate random varible: MAX Time: [step= 1/10, time= 39.8750 secs, global max= 58.14 < 58.23=barycenter]-[step= 1/20, time= 533.5000 secs, global max= 58.1486 < 58.23=barycenter]-[step= 1/30, time= 2.5255e+003 secs, global max= 58.1486 < 58.23=barycenter]  The price of Optimum in Stackelberg games (to be updated)A. C. Kaporis, P. G. Spirakis,  Electronic Colloquium in Computational Complexity (ECCC' 05), Report No. 56 (2005), University of Trier. Also,  technical report in:  Dynamically Evolving, Large-Scale Information Systems (DELIS), supported by Future and Emerging Technologies programme of the EU under contract 001907.  Partitioning networks into classes of mutually isolated nodesJ. Diaz, A.C. Kaporis, L.M. Kirousis, X. Perez, European Conference on Complex Systems (ECCS '05), Paris, 14-18 November 2005  ISB-Tree: A New Indexing Scheme with Efficient Expected BehaviourA.C. Kaporis, C. Makris, G. Mavritsakis, S. Sioutas, A. Tsakalidis, K. Tsichlas, C. Zaroliagis, 16th Annual International Symposium on Algorithms and Computation (ISAAC '05), December 19 - 21, 2005, Sanya, Hainan, China.  Experimental results for Stackelberg scheduling strategies.  A. C. Kaporis, L. M. Kirousis, E. I. Politopoulou, P. G. Spirakis, 4th International Workshop on Efficient and Experimental Algorithms (WEA '05), Springer Verlag, Lecture Notes in Computer Science 3503, 77-89, Santorini Islands, Greece, 2005  Improved bounds for finger search on a RAM.  Alexis C. Kaporis, Christos Makris, Spyros Sioutas, Athanasios Tsakalidis, Kostas Tsichlas, Christos Zaroliagis, 11th Annual European Symposium on Algorithms (ESA '03), Budapest, Hungary.  How to prove conditional randomness using the principle of deferred decisions. A. C. Kaporis, L. Kirousis, Y. Stamatiou, Special Volume on Computational Complexity and Statistical Physics, Santa Fe Institute of Technology, Academic Press.  The probabilistic analysis of a greedy satisfiability algorithm.   A. C. Kaporis, L. M. Kirousis, E. G. Lalas, Random Structures and Algorithms, Wiley.  Lower bounds to the conjectured threshold value for the 3-SAT problem. A. C. Kaporis, L. M. Kirousis, E. G. Lalas,  4th Pan-Hellenic Logic Symposium (PLS '03), Thessaloniki, Greece  Selecting complementary pairs of literals.  A. C. Kaporis, L. M. Kirousis, E. G. Lalas, Electronic Notes in Discrete Mathematics, Elsevier Science, 16 (2003)  The probabilistic analysis of a greedy satisfiability algorithm.   Alexis C. Kaporis, Lefteris M. Kirousis, Efthimios G. Lalas, 10th Annual European Symposium on Algorithms (ESA '02) Rome, Italy. Lecture Notes in Computer Science, Springer-Verlag, Vol: 2461/2002, January 2002, pp. 574-585. Also in 5th International Symposium on the Theory and Applications of Satisfiability Testing (SAT '02), Cincinnati, USA. Also in journal: Random Structures and Algorithms, Wiley,  28(4), 444--480.  The unsatisfiability threshold revisited. A. C. Kaporis, L. M. Kirousis, Y. C. Stamatiou Malvina Vamvakari and M. Zito, Discrete Applied Mathematics, Vol. 22, Issue 2, 1525--1538, Elsevier. A preliminary version appeared in: 16th Annual IEEE Symposium on Logic in Computer Science (LICS '01) affiliated Workshop on Theory and Applications of Satisfiability Testing (SAT '01), Boston, USA  Coupon collectors, q-binomial coefficients and the unsatisfiability threshold. Alexis C. Kaporis, Lefteris M. Kirousis, Yannis C. Stamatiou, Malvina Vamvakari, and Michele Zito. ICTCS 01, LNCS 2202, pp. 328.  A note on the non-colorability threshold of a random graph. Alexis C. Kaporis, Lefteris M. Kirousis, Yannis C. Stamatiou. Electronic Journal of Combinatorics, Volume 7(1) 2000 R 29  Corrigendum to: ''A note on the non-colorability threshold of a random graph''.  Ioannis Giotis, Alexis C. Kaporis, Lefteris M. Kirousis. Electronic Journal of Combinatorics, Volume 7(1) 2000 R 29 Comments.  Locating information with uncertainty in fully interconnected networks with applications to world wide web information retrieval. Alexis C. Kaporis, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yannis C. Stamatiou, and Elias C. Stavropoulos. Computer Journal, Volume 44, Issue 4, pp. 221-229.     Last update: July 8 2008