Markakis Vangelis | Department of Informatics

Assistant Professor

Diploma of Electrical and Computer Engineering, National Technical University of Athens (NTUA), 2000.

M.Sc. in Computer Science, Georgia Institute of Technology, USA, 2004

Ph.D. in Computer Science, Georgia Institute of Technology, USA, 2005

Office:

Main Building, Antoniadou Wing, 4th floor

Email:

markakis AT aueb gr

Telephone:

+30 210 8203 467

WebPage:

http://pages.cs.aueb.gr/~markakis

Office Hours:

Research Interests:

Theoretical computer science, design and analysis of algorithms, approximation algorithms, combinatorial optimization
Game theory, microeconomics, mechanism design, applications in auctions, voting systems and social networks

Dissertations:

Computational aspects of game theory and microeconomics, διδακτορική διατριβή, Georgia Institute of Technology, USA, 2005.

Selected Publications:

1. H. Bosse, J. Byrka, E. Markakis. New algorithms for approximate Nash equilibria in bimatrix games. Theoretical Computer Science 411(1), pp. 164-173, 2010.

2. M. N. Kolountzakis, R. J. Lipton, E. Markakis, A. Mehta, N. K. Vishnoi. On the Fourier spectrum of symmetric Boolean functions. Combinatorica 29(3), pp. 363-387, 2009.

3. K. Apt, V. Conitzer, M. Guo, E. Markakis. Welfare Undominated Groves Mechanisms. Workshop on Internet and Network Economics (WINE), pp. 426-437, 2008.

4. S. Khot, R. Lipton, E. Markakis, A. Mehta. Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions, Algorithmica, 52(1), pp. 3--18, 2008.

5. H. Hatami, A. Magen, E. Markakis. Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to l1 Embeddability of Negative Type Metrics. SIAM Journal on Discrete Math 23(1), pp. 178-194, 2008.

6. R. Lipton, E. Markakis, E. Mossel, A. Saberi. On Approximately Fair Allocations of Indivisible Goods. ACM Conference on Electronic Commerce, pp. 125-131, 2004.

7. R. Lipton, E. Markakis, A. Mehta. Playing Large Games using Simple Strategies. ACM Conference on Electronic Commerce (EC), pp. 36-41, 2003.

8. K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. V. Vazirani. Greedy Facility Location Algorithms Analyzed using Dual Fitting with Factor-Revealing LP. Journal of the ACM, 50 (6), pp. 795--824, November 2003.

Selected Projects:

Analysis of Mechanisms for Sponsored Search Auctions (AMESA). EuroNF Network of Excellence.

Other Activities:

Member of COST action IC0602: Algorithmic Decision Theory
Program Committee memberships: ACM Conference on Electronic Commerce (EC), 2006, 2008-2010, Workshop on Internet and Network Economics (WINE), 2006-2008, 2010, Symposium on Algorithmic Game Theory (SAGT), 2010, International Conference on World Wide Web (WWW), 2008.