Konstantinos (Costis) Georgiou

 

Assistant Professor

Department of Combinatorics & Optimization

Faculty of Mathematics

University of Waterloo

 

200 University Avenue West

Waterloo, ON, N2L 3G1

Canada

 

Office: MC 6316

Phone: +1 (519) 888 4567 ext 37563

Fax: +1 (519) 725 5441

 

e-mail: k * (number two) * (my last name) AT uwaterloo d0t ca

 


 

Education        Publications     Teaching          C&O Reading Group              URprogram-s14          Service            Non Academic Stuff

 


Education

 

Thesis: Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations

Supervised by Avner Magen & Toni Pitassi.

 

Sponsored by the Departments of Mathematics, Informatics & Telecommunications, M.I.TH.E (University of Athens), the Department of Electrical and Computer Engineering (National Technical University of Athens), and by the Department of Computer Engineering and Information (University of Patras).

Thesis: Unfairness in Online Scheduling

Supervised by Elias Koutsoupias (2004)

 

 


 

Research Interests

 

Convex & Combinatorial Optimization, Approximation Algorithms, Game Theory, Hardness of Approximation

 


 

Conference Publications

 

·         Lift & Project Systems Performing on the Partial Vertex Cover Polytope

With Edward Lee

To appear in the 34th Foundations of Software Technology and Theoretical Computer Science (FSTTCS’14)

Also in arXiv: 1409.6365 (2014) [pdf]

 

·         The Multi-source Beachcombers' Problem

      With Jurek Czyzowicz, Leszek Gasieniec, Evangelos Kranakis and Fraser MacQuarrie

      To appear in the 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS’14)

 

·         Stable Marriage with General Preferences

With Linda Farczadi and Jochen Könemann

To appear in the 7th International Symposium on Algorithmic Game Theory (SAGT’14)

Also in arXiv:1407.1853 (2014) [pdf]

 

·         The Beachcombers' Problem: Walking and Searching with Mobile Robots

      With Jurek Czyzowicz, Leszek Gasieniec, Evangelos Kranakis and Fraser MacQuarrie

      To appear in the 21st  International Colloquium on Structural Information and Communication Complexity (SIROCCO’14)

      Also in arXiv:1304.7693 (2013) [pdf]

 

·         Excuse Me! or The Courteous Theatregoers' Problem

With Evangelos Kranakis, Danny Krizanc

7th International Conference on Fun With Aalgorithms (FUN’14)

Also in arXiv:1403.1988 (2014) [pdf]

 

·         Network Bargaining with General Capacities

With Linda Farczadi and Jochen Könemann

21st European Symposium on Algorithms (ESA’13)

Also in arXiv:1306.4302 (2013) [pdf]

 

·         On Integrality Ratios for Assymetric TSP in the Sherali-Adams Hierarchy

With Joseph Cheriyan, Zhihan Gao and Sahil Singla

40th International Colloquium on Automata, Languages and Programming (ICALP’13) [pdf]

Also in arXiv:1405.0945 (2014) [pdf]

 

·         Understanding Set Cover: Sub-exponential Time Approximations and Lift-and-Project Methods

      With Eden Chlamtac and Zac Friggstad

      17th Workshop on Algorithms and Data Structures (WADS’13)

Also in arXiv:1204.5489 (2012) [pdf]

 

·         Social Exchange Networks With Distant Bargaining

      With George Karakostas, Jochen Könemann and Zuzanna Stamirowska

      19th Annual International Computing and Combinatorics Conference (COCOON'13) [pdf]

 

·         Complexity of Barrier Coverage with Relocatable Sensors in the Plane

      With S. Dobrev, S. Durocher, M. Eftekhari, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny, S. Shende, J. Urrutia

      8th International Conference on Algorithms and Complexity (CIAC'13) [pdf]

 

·         Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection

      With Per Austrin and Siavosh Benabbas

      24th Symposium on Discrete Algorithms (SODA'13) [pdf]

      Also in arXiv:1205.0458 (2012) [pdf]

 

With Chaitanya Swamy

      23rd Symposium on Discrete Algorithms (SODA'12) [pdf]

 

With Siavosh Benabbas, Siuon Chan and Avner Magen

31st Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) [pdf]

Also in Electronic Colloquium on Computational Complexity (ECCC), TR 10-169

 

With Avner Magen and Iannis Tourlakis.

      29th Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009) [pdf]

 

With Avner Magen and Madhur Tulsiani.

12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2009) [pdf]
and in Electronic Colloquium on Computational Complexity (ECCC), TR 096-061

 

With Periklis Papakonstantinou.

11th International Conference on Theory and Applications of Satisfiability Testing (SAT 2008) [pdf]

 

With Avner Magen and Iannis Tourlakis.

13th Conference on Integer Programming and Combinatorial Optimization (IPCO 2008) [pdf]

 

With Paul Medvedev, Gene Myers and Michael Brudno

7th Workshop on Algorithms in Bioinformatics (WABI 2007) [pdf]

 

With Avner Magen, Toniann Pitassi and Iannis Tourlakis.

48th IEEE Symposium of Foundations of Computer Science (FOCS 2007) [pdf]
and in Electronic Colloquium on Computational Complexity (ECCC), TR 06-152

 

 

Journal Publications

 

·         Black-Box Reductions for Cost-Sharing Mechanism Design

With Chaitanya Swamy

Games and Economic Behavior (2013) [pdf]

 

·         Social Exchange Networks With Distant Bargaining

      With George Karakostas, Jochen Könemann and Zuzanna Stamirowska

      Theoretical Computer Science (2013) [pdf]

 

With Siavosh Benabbas, Avner Magen and Madhur Tulsiani.

Theory of Computing (2012) [pdf]

 

With Avner Magen, Toniann Pitassi and Iannis Tourlakis.

SICOMP (2010) [pdf]

 

With Evangelos Kranakis and Danny Krizanc.

Discrete Mathematics (2009) [pdf]

 

With Evangelos Kranakis, Ricardo Marcelin-Jimenez, Sergio Rajsbaum, Jorge Urrutia.

International Journal of Distributed Sensor Networks (2005) [pdf]

 

 

Manuscripts

 

·         Efficient Algorithms for Solving Hypergraphic Steiner Tree Relaxations in Quasi-Bipartite Instances

      With Isaac Fung, Jochen Könemann and Malcolm Sharpe

      arXiv:1202.5049 (2011) [pdf]

 

·         Expansion Fools the Sherali-Adams System: Compromising Local and Global Arguments

With Avner Magen.

Technical Report CSRG-587,University of Toronto (2008) [pdf]

 

 

Theses

 

My PhD thesis, under the supervision of Avner Magen and Toni Pitassi (2010) [pdf]

 

My master thesis, under the supervision of Elias Koutsoupias (2004)

 


Teaching

 

University of Waterloo, Dept. of Combinatorics and Optimization (Instructor)

 

“I’m a refrigerator” (?), and a kind message.

The instructor, as seen by winter14 students (either co250 or co372) – thanks for the pic!

Student’s opinion of the instructor.

How does a fun class look like? Of course like this.

And the fun goes on. Here is why.

And yes, a math course can be fun. Why? It is trivial!

 

University of Toronto, Dept. of Computer Science (Teaching Assistant)

 

National Technical University of Athens, School of Electrical and Computer Engineering (Teaching Assistant)

 

University of Athens, Dept. of Mathematics and Dept. of Informatics (Teaching Assistant, Graduate courses)

 

University of Athens, Dept. of Mathematics (Teaching Assistant)

 

University of Athens, Dept. of Mathematics (Lab Assistant)

 


Service

 

Member of Program Committee.

Member of Program Committee.

Member of Program Committee.

Organizer of a session in LP and SDP hierarchies, in the cluster of ``Combinatorial Optimization.''

Member of Program Committee.

Local Organizer.

 


Non Academic Stuff

 

This is what we made in 101 hours out of the following (randomly chosen) ingredients.

Title: Note by Note

An item to be used: Bottle of wine.

A phrase to be used: We are going home, Candy. We are going home.