Computer Science Project

Evangelos Markakis - Curriculum Vitae

P ERSONAL D ATA

Birth: September 28, 1977, Athens, Greece

Address: Patision 76, 10434, Athens, Greece

Phone: +30-210-****-***

Current Position: Lecturer

E-mail: ********@*****.***

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

E DUCATION

Georgia Institute of Technology, Atlanta, Georgia, USA

Ph.D. in Computer Science (Algorithms, Combinatorics, and Optimization Program), 2005.

Dissertation Topic: Computational Aspects of Game Theory and Microeconomics

Advisor: Richard J. Lipton

M.Sc. in Computer Science, 2004.

GPA: 4/4

National Technical University of Athens, Athens, Greece

Diploma (5-year B.Sc. degree with thesis) in Electrical and Computer Engineering, 1995-2000.

Thesis: Logics of Knowledge and Belief - Belief Revision

Advisor: Stathis Zachos

GPA: 9.36/10 (ranked 2nd out of 250)

E MPLOYMENT - P OSITIONS HELD

March 2009 - present: Lecturer, Athens University of Economics and Business, Dept. of Informatics,

Athens, Greece (of cial appointment started in June 2010)

Teaching: Data Structures, Game Theory and Decision Theory, Cryptography and Applications (M.Sc.

course), Special Topics in Theoretical Computer Science (M.Sc. course).

January 2007 - July 2008: Postdoctoral researcher, CWI (Center for Math and Computer Science), Ams-

terdam, the Netherlands

Research: Supported by the EU Marie-Curie Research Training Network ADONET, and by the NWO

research project DIACODEM (Distributed and Adaptive Collective Decision Making).

August 2005 - December 2006: Postdoctoral researcher, University of Toronto, Toronto, ON, Canada

Teaching: Introduction to the Theory of Computation, Fall 2005 and Fall 2006.

Research: Supervised and supported by Prof. Avner Magen.

August 2000 - August 2005: PhD candidate, Georgia Institute of Technology, Atlanta, Georgia, USA

Teaching Assistant for the course Introduction to the Theory of Computation, Spring 2002.

Research Assistant, Fall 2000 - Fall 2001 and Summer 2002 - Summer 2005. Supported by NSF grants

of Prof. Dick Lipton.

R ESEARCH I NTERESTS

Theoretical Computer Science, Approximation Algorithms, Combinatorial Optimization,

Game Theory and Mathematical Economics, Algorithmic Game Theory,

Auctions and Mechanism Design, Voting Theory, Social Networks, Applications to Electronic Com-

merce.

H ONORS AND AWARDS

Recipient of the Microsoft award for the External Research Program: Beyond Search: Semantic Com-

puting and Internet Economics, jointly with Sander Bohte, Nicole Immorlica and Han La Poutr, 2008.

e

Best student paper award (ACM Conference on Electronic Commerce, EC 2003) for the paper On the

Core of the Multicommodity Flow Game, co-authored with Amin Saberi.

Dean s fellowship, College of Computing, Georgia Institute of Technology, 2000-2001 (a fellowship in-

tended for 1st year phd students).

Annual scholarship from the State Scholarships Foundation of Greece for high academic performance,

1995-2000.

Annual scholarship from the Bodosakis Foundation for high academic performance, 1995-2000.

Ranked 2nd in nationwide exams for college admission, Greece, 1995.

Award from the Greek Mathematical Society, 1994.

R ESEARCH P ROJECTS

Member of the main research team in project THALIS-AGT (Algorithmic Game Theory), THALIS re-

search funding program (co- nanced by the European Social Fund and Greek national funds). Bud-

get: 600,000. Duration: 1/10/2011 - 30/9/2015.

Member of the main research team in project THALIS-ALGONOW (Algorithms of today: Social net-

works, data streaming, resource allocation and power management in communication and comput-

ing system), THALIS research funding program (co- nanced by the European Social Fund and Greek

national funds). Budget: 600,000. Duration: 1/10/2011 - 30/9/2015.

Member of the main research team in project INCEPTION (Incentives Driven Participatory Sensing),

ARISTEIA research funding program (co- nanced by the European Social Fund and Greek national

funds). Budget: 200,000. Duration: 15/10/2012 - 14/10/2014.

Project Coordinator in DDCOD (Decision Making over Decentralized Combinatorial Domains), fund-

ing program for the support of postdoctoral researchers (supported postdoc: Orestis Telelis). Budget:

82,000. Duration: 28/3/2012 - 27/3/2015.

Principal Investigator in PEBE3: Social Networks - Models and Diffusion Methods (AUEB - Basic

Research Funding Program). Budget: 7,500. Duration: 1/3/2011 - 29/2/2012.

Member of the coordinating team in project AMESA (Analysis of Mechanisms for Sponsored search

Auctions), EU FP7 Network of Excellence EURO-NF, 1-year SJRP, Budget: 45,000. Duration: 1/11/2009

- 31/10/2010.

M EMBERSHIP IN O THER EU P ROJECTS /N ETWORKS

Management Committee member of COST Action IC1205 on Computational Social Choice, 2012-

present.

Management Committee member of COST Action IC0602 on Algorithmic Decision Theory, 2009-2011.

P ROGRAM C OMMITTEE M EMBERSHIPS IN C ONFERENCES /W ORKSHOPS

IJCAI 2013: 23rd International Joint Conference on Arti cial Intelligence, Beijing, China, August 2013.

EC 2013: 14th ACM Conference on Electronic Commerce, Philadelphia, PA, USA, June 2013.

CoopMAS 2013: 4th Workshop on Cooperative Games in Multi-agent Systems, Saint Paul, Minnesota,

May 2013.

WINE 2012: 8th Workshop on Internet and Network Economics, Liverpool, UK, December 2012.

AAAI 2012: 26th National Conference of the American Association for Arti cial Intelligence, Toronto,

ON, Canada, July 2012.

EC 2012: 13th ACM Conference on Electronic Commerce, Valencia, Spain, June 2012.

AAMAS 2012: 11th International Conference on Autonomous Agents and Multi-agent Systems, Va-

lencia, Spain, June 2012.

ISCO 2012: 2nd International Symposium on Combinatorial Optimization, Athens, Greece, April

2012.

WWW 2012: 21st International World Wide Web Conference, Track: Internet Monetization and In-

centives, Lyon, France, April 2012.

AAAI 2011: 25th National Conference of the American Association for Arti cial Intelligence, San

Francisco, California, USA, August 2011.

EC 2011: 12th ACM Conference on Electronic Commerce, San Diego, California, USA, June 2011.

AAMAS 2011: 10th International Conference on Autonomous Agents and Multi-agent Systems, Taipei,

Taiwan, May 2011.

CoopMAS 2011: 2nd Workshop on Cooperative Games in Multi-agent Systems, Taipei, Taiwan, May

2011.

WINE 2010: 6th Workshop on Internet and Network Economics, Stanford, California, USA, December

2010.

SAGT 2010: 3rd Symposium on Algorithmic Game Theory, Athens, Greece, October 2010.

EC 2010: 11th ACM Conference on Electronic Commerce, Boston, Massachusetts, USA, June 2010.

CoopMAS 2010: 1st Workshop on Cooperative Games in Multi-agent Systems, Toronto, ON, Canada,

May 2010.

EC 2009: 10th ACM Conference on Electronic Commerce, Stanford, California, USA, June 2009.

AAMAS 2009: 8th International Conference on Autonomous Agents and Multi-agent Systems, Bu-

dapest, Hungary, May 2009.

SOFSEM 2009: 35th International Conference on Current Trends in Theory and Practice of Computer

Science, Track: Game Theoretic Aspects of E-commerce, Spindleruv Mlyn, Czech Republic, January

2009.

WINE 2008: 4th Workshop on Internet and Network Economics, Shanghai, China, December 2008.

COMSOC 2008: 2nd International Workshop on Computational Social Choice, Liverpool, UK, Septem-

ber 2008.

EC 2008: 9th ACM Conference on Electronic Commerce, Chicago, Illinois, USA, June 2008.

WWW 2008: 17th International World Wide Web Conference, Track: Internet Monetization, Beijing,

China, April 2008.

WINE 2007: 3rd Workshop on Internet and Network Economics, San Diego, California, USA, Decem-

ber 2007.

WINE 2006: 2nd Workshop on Internet and Network Economics, Patras, Greece, December 2006.

AAAI Workshop on Auction Mechanisms for Robot Coordination, Boston, Massachusetts, USA, July

2006.

EC 2006: 7th ACM Conference on Electronic Commerce, Ann Arbor, Michigan, USA, June 2006.

O RGANIZATION OF C ONFERENCES /W ORKSHOPS

Member of the organizing committee of ACAC 2013: 8th Athens Colloquium on Algorithms and

Complexity, Athens, Greece, August, 2013.

Member of the organizing commitee of ISCO 2012: 2nd International Symposium on Combinatorial

Optimization, Athens, Greece, April 17-21, 2012.

Member of the organizing committee of ACAC 2009: 4th Athens Colloquium on Algorithms and

Complexity, Athens, Greece, August 20-21, 2009.

E DITORIAL W ORK

Co-editor, together with I. Milis and V. Th. Paschos, of TCS special issue on the topic Combinatorial

Optimization: Theory of Algorithms and Complexity, forthcoming, 2013.

Co-editor, together with A. R. Mahjoub, I. Milis and V. Th. Paschos, of the Proceedings of ISCO 2012:

2nd International Symposium on Combinatorial Optimization, Athens, Greece, April 17-21, 2012.

Lecture Notes in Computer Science 7422, Springer 2012, ISBN 978-3-642-32146-7.

Co-editor, together with I. Milis, of the Proceedings of ACAC 2009: 4th Athens Colloquium on Al-

gorithms and Complexity, Athens, Greece, August 20-21, 2009. EPTCS 4 (Electronic Proceedings in

Theoretical Computer Science).

O THER A CTIVITIES

Reviewing: I have served as a referee for the following conferences and journals:

Journal reviews: ACM TEAC (ACM Transactions on Economics and Computation), Algorithmica,

Theoretical Computer Science, SIAM Journal on Computing, INFORMS Journal on Computing, Op-

erations Research Letters, Games and Economic Behavior, Journal of Arti cial Intelligence Research,

Journal of Discrete Algorithms, Journal of Autonomous Agents and Multi-Agent Systems, IEEE

Transactions on Automation Science and Engineering, Information Processing Letters.

Conference reviews: IEEE Symposium on Foundations of Computer Science (FOCS), ACM Sym-

posium on Theory of Computing (STOC), ACM-SIAM Symposium on Discrete Algorithms (SODA),

IEEE Conference on Computational Complexity (CCC), International Colloquium on Automata, Lan-

guages and Programming (ICALP), European Symposium on Algorithms (ESA), ACM Conference on

Electronic Commerce (EC), Workshop on Internet and Network Economics (WINE), Symposium on

Algorithmic Game Theory (SAGT), Workshop on Combinatorial and Algorithmic Aspects of Net-

working (CAAN), Computing and Combinatorics Conference (COCOON).

Seminars: I have organized or co-organized the following seminars:

Theory seminar (weekly meeting on theoretical computer science), University of Toronto, Dept. of

Computer Science, August 2005 - December 2006.

Theory tea (weekly meeting on theoretical computer science), Athens University of Economics and

Business, Dept. of Informatics, February 2010 - present.

I NVITED S PEAKER AT C ONFERENCES /W ORKSHOPS

BRICKS (Basic Research in Informatics for Creating the Knowledge Society) Workshop on Game The-

ory and Multiagent Systems, CWI, Amsterdam, June 30, 2009.

PHAC Workshop (Preference Handling and Aggregation on Combinatorial domains), LIP6, Paris,

June 23-24, 2009.

C ONTRIBUTED TALKS AT C ONFERENCES /W ORKSHOPS WITH I NVITED PARTICIPATION

Dagstuhl seminar on Interface of Computation, Game Theory, and Economics, Dagstuhl, Germany,

April 14-19, 2013.

Summer school on Algorithmic Game Theory, Samos, Greece, July 14-21, 2012.

Dagstuhl seminar on Computation and Incentives in Social Choice, Dagstuhl, Germany, March 4-9,

2012.

GREAT Workshop (Greece Economic and Algorithmic Theory Week), Paros, Greece, July 24-29, 2011.

Workshop on Advances in Algorithmic Game Theory, Amsterdam, the Netherlands, September

2-3, 2010.

Dagstuhl seminar on Computational Foundations of Social Choice, Dagstuhl, Germany, March 7-

12, 2010.

Dagstuhl seminar on Fair Division, Dagstuhl, Germany, June 24-29, 2007.

INFORMS 2005 Annual Meeting, Session: Auctions, San Francisco, November 13-16, 2005.

TALKS IN D EPARTMENTS /S EMINARS /W ORKSHOPS AND OTHER EVENTS

CWI, Center for Math and Computer Science, Amsterdam, the Netherlands, February 2012.

Luiss University, Department of Economics, Rome, Italy, September 2011.

Universit di Roma La Sapienza, Dipartimento di Ingegneria Informatica, Rome, Italy, September

a

2011.

Universit Paris-Dauphine, LAMSADE, Paris, France, February 2011.

e

London School of Economics, Department of Management, Math. Programming seminar, London,

UK, October 2010.

COMSOC, 3rd International Workshop on Computational Social Choice, Dusseldorf, Germany, Septem-

ber 2010.

Athens Colloquium on Algorithms and Complexity, Athens, Greece, 2006 - 2010 (annually every

August).

SING6: 6th Spain-Italy-Netherlands Meeting on Game Theory, Palermo, Italy, July 2010.

Max Planck Institut fur Informatik, Saarbrucken, Germany, March 2010.

Aachen University, Aachen, Germany, June 2009.

SED (Society for Economic Design) Conference on Economic Design, University of Maastricht, Maas-

tricht, the Netherlands, June 2009.

University of Amsterdam, Institute of Language, Logic and Computation (ILLC), Amsterdam, the

Netherlands, April 2009.

SING4: 4th Spain-Italy-Netherlands Meeting on Game Theory, Wroclaw, Poland, June 2008.

Universit dAnnunzio, Pescara, Italy, April 2008.

a

University of Aarhus, Department of Computer Science, Aarhus, Denmark, February 2008.

University of Maastricht, Department of Quantitative Economics, Maastricht, the Netherlands, Octo-

ber 2007.

University of Southampton, Department of Electronics and Computer Science, Seminar of the IAM

group (Intelligence, Agents and Multimedia), Southampton, UK, September 2007.

Universit d Annunzio, Pescara, Italy, June 2007.

a

Stanford University, Department of Computer Science, Palo Alto, California, USA, May 2007.

Tilburg University, Department of Econometrics and Operations Research, Game Theory Seminar,

Tilburg, the Netherlands, May 2007.

University of Toronto, Department of Economics, Toronto, ON, Canada, November 2006.

DIAMANT/Spinoza Intercity Seminar on Algebra and Symmetries in Combinatorics and Optimiza-

tion, Amsterdam, the Netherlands, June 2006.

University of Waterloo, Department of Combinatorics and Optimization, Tutte Seminar, Waterloo,

ON, Canada, March 2006.

University of Athens, Department of Computer Science, Theory Seminar, Athens, Greece, February

2006.

University of Crete, Department of Mathematics, Discrete Math Seminar, Iraklio, Greece, February

2006.

National Technical University of Athens, Theory seminar, Athens, Greece, February 2006.

CWI, Center for Math and Computer Science, Amsterdam, the Netherlands, February 2006.

University of Amsterdam, Institute of Language, Logic and Computation (ILLC), February 2006.

National University of Singapore, Department of Computer Science, Singapore, December 2005.

McMaster University, Department of Computing and Software, Hamilton, ON, Canada, October

2005.

Yahoo Research Labs, Pasadena, California, USA, April 2005.

University of Waterloo, Department of Combinatorics and Optimization, Algorithms and Complexity

Seminar, Waterloo, ON, Canada, March 2005.

University of Toronto, Department of Computer Science, theory seminar, Toronto, ON, March 2005.

S UPERVISION OF S TUDENTS AND P OSTDOCS

Svetlana Obraztsova, Postdoctoral researcher, January 2013 - present.

Orestis Telelis, Postdoctoral researcher, March 2012 - present.

Ioannis Giotis, Postdoctoral researcher, November 2012 - present.

Georgios Mpirmpas, PhD candidate, to start in February 2013.

Christos Alatzidis (M.Sc. thesis, 2011-2012)

Penny Samartzi (M.Sc. thesis, 2011-2012)

Angelos Asimakopoulos (M.Sc. thesis, 2010-2011)

Christina Aretha (M.Sc. thesis, 2010-2011)

Maria Sotiri (M.Sc. thesis, Fall 2010)

Ioanna Anastasopoulou (M.Sc. thesis, 2009-2010)

Supervised B.Sc. students: Christos-Alexandros Psomas (2010-2011), Lefteris Mpetsos (2011), Alexan-

dra Papoutsaki (2010-2011), Yanos Sorokos (2010).

P UBLICATIONS

Citation indices

Citations: 950 (according to Google scholar, Nov. 10, 2012)

h-index: 15

i10-index: 20

Book chapters/Surveys

P. Maille, E. Markakis, M. Naldi, G. D. Stamoulis, B. Tuf n. Sponsored Search Auctions: An Overview of

Research with Emphasis on Game Theoretic Aspects. Journal of Electronic Commerce Research (ECR),

12(3), pp. 265-300, 2012.

E. Elkind, E. Markakis. Game-theoretic Foundations of Multiagent Systems. Chapter 17 in Multi-Agent

Systems, edited by Gerhard Weiss, MIT Press, 2012.

Refereed Conference Publications

V. Tzoumas, C. Amanatidis, E. Markakis. A Game-theoretic Analysis of a Competitive Diffusion Process

over Social Networks. Workshop on Internet and Network Economics (WINE), pp. 1-14, 2012.

E. Markakis, O. Telelis. Uniform Price Auctions: Equilibria and Ef ciency. Symposium on Algorithmic

Game Theory (SAGT), pp. 227-238, 2012.

Y. Zick, E. Markakis, E. Elkind, Stability Via Convexity and LP Duality in OCF Games, AAAI, 2012.

G. Chalkiadakis, E. Markakis, N. R. Jennings. Coalitional Stability in Structured Environments. Interna-

tional Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 779-786, 2012.

E. Bampis, D. Letsios, G. Lucarelli, E. Markakis, I. Milis. On Multiprocessor Temperature-Aware Schedul-

ing Problems. Joint International Conference on Frontiers in Algorithmics and Algorithmic Aspects in Informa-

tion and Management (FAW-AAIM), pp. 149-160, 2012.

E. Markakis, C.A. Psomas. On Worst-Case Allocations in the Presence of Indivisible Goods. Workshop

on Internet and Network Economics (WINE), pp. 278-289, 2011.

K. R. Apt, E. Markakis. Diffusion in Social Networks with Competing Products. Symposium on Algorith-

mic Game Theory (SAGT) pp. 212-223, 2011.

N. Immorlica, E. Markakis, G. Piliouras. Coalition Formation and Price of Anarchy in Cournot Oligopolies,

Workshop on Internet and Network Economics (WINE), pp. 270-281, 2010.

E. Markakis, O. Telelis. Discrete Strategies in Keyword Auctions and their Inef ciency for Locally Aware

Bidders, Workshop on Internet and Network Economics (WINE), pp. 523-530, 2010.

I. Caragiannis, D. Kalaitzis, E. Markakis. Approximation Algorithms and Mechanism Design for Mini-

max Approval Voting, AAAI, pp. 737-742, 2010.

R. Gomes, N. Immorlica, E. Markakis. Externalities in Keyword Auctions: an Empirical and Theoretical

Assessment, Workshop on Internet and Network Economics (WINE), pp. 172-183, 2009.

K. R. Apt, E. Markakis. Sequential Bidding in the Bailey-Cavallo Mechanism, Workshop on Internet and

Network Economics (WINE), pp. 483-490, 2009.

S. Koenig, X. Zheng, C. Tovey, R. Borie, P. Kilby, E. Markakis, P. Kescinocak. Agent Coordination with

Regret Clearing. AAAI, pp. 101 107, 2008.

K. R. Apt, V. Conitzer, M. Guo, E. Markakis. Welfare Undominated Groves Mechanisms. Workshop on

Internet and Network Economics (WINE), pp. 426 437, 2008.

G. Chalkiadakis, E. Elkind, E. Markakis, N. Jennings. Overlapping Coalition Formation. Workshop on

Internet and Network Economics (WINE), pp. 307 321, 2008.

Y. Bachrach, E. Markakis, A. D. Procaccia, J. S. Rosenschein and A. Saberi. Approximating Power Indices.

International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 943-***-****.

H. Bosse, J. Byrka, E. Markakis. New Algorithms for Approximate Nash Equilibria in Bimatrix Games,

Workshop on Internet and Network Economics (WINE), pp. 17 29, 2007.

H. Hatami, A. Magen, E. Markakis. Integrality gaps of semide nite programs for Vertex Cover and

relations to 1 embeddability of Negative Type metrics, APPROX-RANDOM, pp. 164-179, 2007.

G. Chalkiadakis, E. Markakis and C. Boutilier. Coalition Formation Under Uncertainty: Bargaining

Equilibria and the Bayesian Core Stability Concept, Proc. of 6th International Joint Conference on Au-

tonomous Agents and Multiagent Systems (AAMAS), pp. 64-71, 2007.

R. Legrand, E. Markakis, A. Mehta. Approval Voting: Approximation Algorithms and Heuristics for the

Minimax Solution, Proc. of 6th International Joint Conference on Autonomous Agents and Multiagent Systems

(AAMAS), short paper, pp. 198-200, 2007, preliminary version presented in the 1st International Workshop

on Computational Social Choice (COMSOC), 2006.

S. Khot, R. Lipton, E. Markakis, A. Mehta. Inapproximability Results for Combinatorial Auctions with

Submodular Utility Functions, 1st Workshop on Internet and Network Economics (WINE), pp. 92 101, 2005.

M. Lagoudakis, E. Markakis, D. Kempe, P. Keskinocak, S. Koenig, C. Tovey, A. Kleywegt, A. Meyerson,

S. Jain. Auction-based Multi-robot Routing, Robotics: Science and Systems, pp. 343-350, 2005, also ap-

peared as nectar paper in AAAI 2006, journal version to be submitted to Journal of Arti cial Intelligence

Research (JAIR).

R. Lipton, E. Markakis, A. Mehta, N. Vishnoi. On the Fourier Spectrum of Symmetric Boolean Functions

with Applications to Learning Symmetric Juntas, IEEE Conference on Computational Complexity (CCC

2005), pp. 112 119, 2005.

R. Lipton, E. Markakis, E. Mossel, and A. Saberi, On Approximately Fair Allocations of Indivisible

Goods, 5th ACM Conference on Electronic Comerce (EC 2004), pp. 125 131, 2004.

R. Lipton, E. Markakis. Nash Equilibria via Polynomial Equations, Latin American Theoretical Informatics

(LATIN 2004), pp. 413 422, 2004.

E. Markakis, A. Saberi. On the Core of the Multicommodity Flow Game, 4th ACM Conference on Electronic

Commerce (EC 2003), pp. 93-97, 2003. Recipient of the best student paper award. Invited for publication

in special issue of Decision Support Systems.

R. Lipton, E. Markakis, A. Mehta. Playing Large Games using Simple Strategies, 4th ACM Conference on

Electronic Commerce (EC 2003), pp. 36-41, 2003.

M. Mahdian, E. Markakis, A. Saberi, V. V. Vazirani. A Greedy Facility Location Algorithm Analyzed

using Dual Fitting, APPROX-RANDOM, pp. 127 137, 2001.

Journal Publications

M. Guo, E. Markakis, K. R. Apt, V. Conitzer. Undominated Groves Mechanisms. Accepted in Journal of

Arti cial Intelligence Research (JAIR), 2013, to appear.

G. Chalkiadakis, E. Elkind, E. Markakis, M. Polukarov, N. Jennings. Cooperative Games with Overlap-

ping Coalitions. Journal of Arti cial Intelligence Research (JAIR), 39, pp. 179-216, 2010.

H. Bosse, J. Byrka, E. Markakis. New Algorithms for Approximate Nash Equilibria in Bimatrix Games,

Theoretical Computer Science, 411(1), pp. 164-173, 2010.

Y. Bachrach, E. Markakis, A. D. Procaccia, E. Resnick, J. S. Rosenschein and A. Saberi. Approximating

Power Indices. Journal of Autonomous Agents and Multiagent Systems, 20(2), pp. 105-122, 2010.

M. Kolountzakis, R. Lipton, E. Markakis, A. Mehta, N. Vishnoi. On the Fourier Spectrum of Symmetric

Boolean Functions, Combinatorica, 29(3), pp. 363-387, 2009.

H. Hatami, A. Magen, E. Markakis. Integrality gaps of semide nite programs for Vertex Cover and

relations to l1 embeddability of Negative Type metrics, SIAM Journal on Discrete Mathematics, 23(1), pp.

178-194, 2008.

S. Khot, R. Lipton, E. Markakis, A. Mehta. Inapproximability Results for Combinatorial Auctions with

Submodular Utility Functions, Algorithmica, 52(1), pp. 3 18, 2008.

E. Markakis, A. Saberi. On the Core of the Multicommodity Flow Game, Decision Support Systems, 39(1),

pp. 3 10, March 2005.

K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. V. Vazirani. Greedy Facility Location Algorithms Ana-

lyzed using Dual Fitting with Factor-Revealing LP, Journal of the ACM, 50 (6), pp. 795 824, November

2003.

Pending Journal Submissions

E. Bampis, D. Letsios, G. Lucarelli, E. Markakis, I. Milis. On Multiprocessor Temperature-Aware Schedul-

ing Problems. Submitted to Journal of Scheduling, 2012.

K. R. Apt, E. Markakis. Social Networks with Competing Products. Submitted to Fundamenta Informati-

cae, 2012.

G. Chalkiadakis, G. Greco, E. Malizia, E. Markakis, L. Palopoli, F. Scarcello, N. R. Jennings. Coalitional

Stability in Structured Environments. To be submitted to International Journal of Game Theory, 2013.

Contact this candidate