George Karakostas' Homepage

Contact info:

Academic Degrees

• Ph.D in Computer Science, Princeton University, 2000
• MA in Computer Science, Princeton University, 1997
• Diploma in Computer Engineering & Informatics, University of Patras, 1995

Reasearch

Publications 

• Approximation schemes for Minimum Latency Problems  S. Arora, G. Karakostas, Proceedings ACM STOC 1999
• A 2+epsilon approximation algorithm for the k-MST problem  S. Arora, G. Karakostas, Proceedings ACM-SIAM SODA 2000
• On the complexity of the intersection of FSA's  G. Karakostas, R.J. Lipton, A. Viglas, Proceedings IEEE Complexity 2000
• Effective caching of web objects using Zipf's laws  D. Serpanos, G. Karakostas, W.H.Wolf, Proceedings IEEE ICME 2000
• Practical LFU implementation for web caching  G. Karakostas, D. Serpanos, Technical Report CS Princeton Univ. TR-622
• Results on Approximation Algorithms Ph.D. Thesis  (Advisor: Sanjeev Arora), Princeton University, November 2000
• Faster approximation schemes for fractional multicommodity flow problems  G. Karakostas, Proceedings ACM/SIAM SODA 2002. A more complete (journal) version can be found here.
• Practical issues and algorithms for analyzing terrorist networks   T. Carpenter, G. Karakostas, D. Shallcross, Invited paper at WMC 2002
• Exploitation of different types of locality for web caches  G. Karakostas, D. N. Serpanos, Proceedings IEEE ISCC 2002
• A proof for effective and efficient web caching  D. N. Serpanos, G. Karakostas, IEE Electronics Letters, 38(10), pp. 490-492, 2002
• Equilibria for networks with malicious users  G. Karakostas, A. Viglas, Proceedings ISAAC 2003
• Selfish routing in the presence of side constraints  G. Karakostas, S. Kolliopoulos, Tech. report CAS-03-13-GK, Dept. of CAS, McMaster Un., 2003
• General pseudo-random generators from weaker models of computation G. Karakostas, Tech. report CAS-03-16-GK, Dept. of CAS, McMaster Un., 2003 and Proceedings ISAAC 2009
  
• The efficiency of optimal taxes, G. Karakostas, S. Kolliopoulos, Proceedings CAAN 2004
• Edge pricing of multicommodity networks for heterogeneous users, G. Karakostas, S. Kolliopoulos, Proceedings IEEE FOCS 2004
• A better approximation ratio for the Vertex Cover problem, G. Karakostas, Proceedings ICALP 2005 (Preliminary version appeared as ECCC Report TR04-084 and AdvOL Report #2004/13, September/October 2004)
  
• Maximizing throughput in queueing networks with limited flexibility, D. Down, G. Karakostas, Proceedings LATIN 2006 (earlier version presented in MAPSP'05).
• Edge pricing of multicommodity networks for selfish users with elastic demands, G. Karakostas, S. Kolliopoulos, Proceedings COCOON 2006.
• Selfish routing with oblivious users, G. Karakostas, T. Kim, A. Viglas, H. Xia, Proceedings SIROCCO 2007.
• Stackelberg strategies for selfish routing in general multicommodity networks,  G. Karakostas, S. Kolliopoulos, Algorithmica 2007.
• Emergency connectivity in ad-hoc networks with selfish nodes, G. Karakostas, E. Markou, Proceedings LATIN 2008.
• An FPTAS for the minimum total weighted tardiness problem with a fixed number of distinct due dates, G. Karakostas, S. Kolliopoulos, J. Wang, Proceedings COCOON 2009 (also in MAPSP'09).
• On the existence of optimal taxes for network congestion games with heterogeneous users, D. Fotakis, G. Karakostas, S. Kolliopoulos, Proceedings SAGT 2010 (also in EURO XXIV).
  

Courses

•    CS 3MG3  Fall 2002, 2003, 2004, 2005, 2006
•    CS 2CA3  Winter 2008, Fall 2008, 2010
•    CS 2GA3  Fall 2011,  2012
•    CS 3SH3   Winter 2012
•    CS/SE 2C03   Winter 2013
•    SE 3F03    Winter 2010
  
•    SE 3GA3   Fall 2005, 2006, 2007, 2008, 2010, 2011, 2012
•    SE 3G03   Fall 2004
  
•    SE 3H03   Winter 2003, 2004
•    SE 3SH3   Winter 2012
  
•    SE 4O03   Winter 2006, 2007, 2008,  2010
  
•    CAS 744   Winter 2005, 2010, 2011
  
•    CAS 702   Fall 2010, 2012