Elias Koutsoupias' weblog and personal page

I gave a talk during the first Athens Colloquium on Algorithms and Complexity (ACAC 2006): On Mechanisms for Scheduling on Unrelated Machines.

Abstract: The mechanism design problem of scheduling tasks on n unrelated machines, in which the machines are the players of the mechanism, was proposed and studied in the seminal paper of Nisan and Ronen about ten years ago. It was shown there that the approximation ratio of mechanisms is between 2 and n. Despite the central role of the problem in the new area of Algorithmic Mechanism Design, there was no improvement on these bounds. In this talk, I will present some recent approaches and results.

2006.08.26-00:17.00
/Presentations | 0 writebacks | permanent link

With George Christodoulou and Angelina Vidali [CKV07], we improved the lower bound of the approximation ratio for the mechanism-design version of scheduling unrelated machines. The problem was proposed and studied in the 1998 seminal paper of Nisan and Ronen, where it was shown that the approximation ratio of mechanisms is between 2 and n, where n is the number of machines. Their paper brought to the attention of the CS theory community the notion of mechanism design and its algorithmic issues. Despite the central role of the scheduling problem in this area, there was no improvement since the original paper of Nisan and Ronen. We improved the lower bound from 2 to 2.41.

2006.08.25-12:09.00
/Research/Game Theory | 0 writebacks | permanent link

Για ποιους: Προπτυχιακούς φοιτητές κυρίως
Πότε: Δευτέρα 22/05/2006, 12:00-2:00
Πού: Αίθουσα Συνεδριάσεων (1ος όροφος)
Από ποιους: Κυρίως από φοιτητές που πέρασαν τη διαδικασία πρόσφατα.

Την Δευτέρα 22 Μαΐου στις 12:00 διοργανώνεται Ημερίδα Ενημέρωσης για Μεταπτυχιακά σε ΗΠΑ/Καναδά. Στην εκδήλωση θα μιλήσουν κυρίως φοιτητές που έχουν περάσει από αυτή την διαδικασία αιτήσεων και είτε ήδη σπουδάζουν σε κάποιο Πανεπιστήμιο στις ΗΠΑ ή τον Καναδά, είτε θα ξεκινήσουν το Φθινόπωρο τις σπουδές τους εκεί. Η εκδήλωση θα έχει περισσότερο χαρακτήρα συζήτησης μεταξύ φοιτητών. Θα πάρουν μέρος και κάποιοι καθηγητές με εμπειρία από Β. Αμερική.

Η εκδήλωση θα λάβει χώρα στην Αίθουσα Συνεδριάσεων του Τμήματος και θα διαρκέσει περίπου 2 ώρες. Το συνοδευτικό υλικό της Ημερίδας βρίσκεται ήδη σε ένα wiki που έχει δημιουργηθεί γι’ αυτόν τον σκοπό, το οποίο θα βελτιώνεται/ενημερώνεται συνεχώς, στην διεύθυνση: http://www.di.uoa.gr/~diwiki/

2006.05.15-23:21.00
/Student Issues | 2 writebacks | permanent link

I gave a talk at the Athens University of Economics and Business on Feb 2, 2006 on The price of anarchy of congestion games and mechanisms.

Abstract: Ideally, users who share the resources of a system should behave in a way that optimizes the performance of the system. But when users are selfish, they act in a way that optimizes their own individual and usually conflicting objectives. The price of anarchy is an attempt to measure the deterioration of the performance of a system due to selfish behavior of its users or components. I present recent results on the price of anarchy of congestion games.

When the price of anarchy is high, we want to redesign the game or the system to improve its performance. I present approaches such as mechanism design, taxes, and coordination mechanisms that attempt to improve the performance of systems with selfish users.

2006.02.03-08:34.00
/Presentations | 0 writebacks | permanent link

Τα splay trees είναι μια βασική δομή δεδομένων, ένα δυαδικό δένδρο αναζήτησης. Προτάθηκαν στα μέσα της δεκαετίας του 80 απο τους Sleator και Tarzan και υπάρχουν σε πολλές βιβλιοθήκες γλωσσών προγραμματισμού. Ενώ όμως έχει αποδειχθεί ότι έχουν μερικές καταπληκτικές ιδιότητες και είναι πολύ αποτελεσματικά στην πράξη, η απόδοση τους παραμένει ένα μυστήριο. Αυτο αποτυπώνεται με ωραίο τροπο στην splay tree conjecture που λέει ότι τα splay trees έχουν απόδοση ανάλογη του βέλτιστου αλγόριθμου/δομής που γνωρίζει την ακολουθία αιτήσεων εκ των προτέρων.

Η εικασία παραμένει ανοικτή απο το 1985 και αποτελεί ένα απο τα σημαντικότερα ανοικτά προβλήματα στις περιοχές των δομών δεδομένων και των άμεσων αλγόριθμων.

Στις πτυχιακές και διπλωματικές εργασίες θα μελετήσουμε τις βασικές δημοσιεύσεις, θα γράψουμε μια επισκόπηση, και θα πειραματιστούμε με περιπτώσεις του προβλήματος. Σκοπός των υπολογιστικών πειραμάτων θα είναι να:

- Να αποτιμήσουμε τη συμπεριφορά των splay trees για μικρές δομές

- Να κατασκευάσουμε ένα πρόγραμμα που να ελέγχει την ορθότητα της εικασίας για ακολουθίες αιτήσεων συγκεκριμένου μεγέθους.

- Να προσπαθήσουμε να καταρρίψουμε την εικασία κατασκευάζοντας κατάλληλες εισόδους.

Πηγές:

Βιβλία:

Δημοσιεύσεις:

Ιστός:

2005.10.22-20:22.00
/Topics For Theses | 0 writebacks | permanent link

Σχεδιασμός Μηχανισμού για χρονοπρογραμματισμό εργασιών

Θέλουμε να αναθέσουμε ένα σύνολο M εργασιών σε ένα σύνολο Ν επεξεργαστών, έτσι ώστε οι εργασίες να τελείωσουν όσο γίνεται πιο γρήγορα. Το πρόβλημα αυτό ειναι από τα πιο διάσημα της θεωρητικής πληροφορικής και έχουν μελετηθεί πολλές παραλλαγές του. Εδώ μας ενδιαφέρει η περίπτωση που ο κάθε επεξεργαστής μπορέι να εκτελέσει μια εργασία σε χρόνο που γνωρίζει μόνο ο ίδιος. Μπορούμε να τον υποχρεώσουμε να αποκαλύψει το χρόνο αυτό ώστε να ξέρουμε πώς μας συμφέρει να αναθέσουμε τις εργασίες; Υπάρχουν συγκεκριμένοι επιτρεπτοί τρόποι με τους οποίους μπορούμε να το επιτύχουμε (Σχεδιασμός Φιλαλήθη Μηχανισμού).

Στα πλαίσια μιας πτυχιακής/διπλωματικής εργασίας, θα μελετηθούν βασικές εργασίες της σχετικής βιβλιογραφίας και θα δοκιμάσουμε πειραματικά διάφορους μηχανισμούς για την περίπτωση των 3 επεξεργαστών.

Πηγές:

Βιβλία:

Δημοσιεύσεις:

Ιστός:

2005.10.14-16:52.00
/Topics For Theses | 0 writebacks | permanent link

Ένα βασικό ερώτημα στην οικονομική επιστήμη είναι πώς μπορούμε να μοιράσουμε ένα κέικ σε ένα πλήθος καλεσμένων, με δίκαιο τρόπο. Υποθέτουμε πως ο καθένας μπορεί να έχει διαφορετική προτίμηση στα κομμάτια που προτιμά (π.χ ο ένας προτιμά τις φράουλες και τη σοκολάτα, ενω ο άλλος την κρέμα και τα αμύγδαλα). Η έννοια της “δικαιοσύνης” μπορεί να οριστεί με διαφόρους τρόπους, π.χ. μοίρασε το κέικ έτσι ώστε κανένας να μην προτιμά το κόμματι του άλλου, ή έτσι ώστε όλοι να έχουν πάρει κομμάτι που αντιστοιχεί στο 1/Ν της προτίμησης τους, όπου Ν είναι το πλήθος των καλεσμένων. Το πρόβλημα είναι πως δεν γνωρίζουμε εκ των προτέρων τις προτιμήσεις των καλεσμένων και θα τις μάθουμε έμμεσα (π.χ βάζοντας τους έναν ένα να κόψουν κομμάτια).

Το πρόβλημα αυτό, έχει μελετηθεί εκτενώς, κι έχουν προταθεί πολλά πρωτόκολλα κοπής ενός κέικ που ικανοποιούν κάποια κριτίρια δικαιοσύνης. Μια πιο δύσκολη εκδοχή του προβλήματος προκύπτει αν αντί για κέικ θεωρήσουμε ένα σύνολο (αδιαίρετων) αγαθών που θέλουμε να μοιράσουμε δίκαια.

Στα πλαίσια μιας πτυχιακής/διπλωματικής εργασίας, θα μελετηθούν βασικές εργασίες της σχετικής βιβλιογραφίας και θα δοκιμάσουμε να προσαρμόσουμε κάποια πρωτόκολλα κοπής στο πρόβλημα δίκαιης ανάθεσης αγαθών.

Πηγές:

Βιβλία:

Δημοσιεύσεις:

Ιστός:

2005.10.14-16:50.00
/Topics For Theses | 0 writebacks | permanent link

Το k-server πρόβλημα αποτελεί το πιο σημαντικό πρόβλημα στην περιοχή των άμεσων αλγορίθμων (online algorithms), δηλαδή των αλγορίθμων που πρέπει να πάρουν αποφάσεις χωρίς να γνωρίζουν το μέλλον. Στο πρόβλημα αυτό, υπάρχουν k servers (για παράδειγμα τεχνικοί του ΟΤΕ) και ικανοποιούν μια ακολουθία από αιτήσεις (π.χ. βλάβες σε διάφορα σημεία του δικτύου). Για να ικανοποιήσει ένας server μια αίτηση, πρέπει να μετακινηθεί στο σημείο αυτό. Ο σκοπός μας είναι να ελαχιστοποιήσουμε το συνολικό μήκος που διανύουν οι servers (δηλαδή την βενζίνη στην περίπτωση του ΟΤΕ). Το πρόβλημα είναι άμεσο (online) γιατί δεν γνωρίζουμε εκ των πρότερων τα σημεία των αιτήσεων.

Το k-server πρόβλημα μοντελοποιεί πολλά πρακτικά προβλήματα, όπως π.χ. το πως να μετακινούνται οι κεφαλές ενός σκληρού δίσκου. Όπως με τις βλάβες του ΟΤΕ, ούτε σ’ αύτη την περίπτωση μπορούμε να προβλέψουμε ποιό τμήμα του δίσκου θα διαβάσουν και θα γράψουν οι κεφαλές.

Η k-server conjecture λέει ότι υπάρχει άμεσος αλγόριθμος που βρίσκει λύση που σε κάθε περίπτωση είναι το πολύ k φορές χειρότερη από τη βέλτιστη λύση (τη λύση δηλαδή που μπορούμε να πετύχουμε αν γνωρίζουμε την ακολουθία αιτήσεων εκ των προτέρων). Η εικασία αυτή, μαζί με την εικασία για τα splay trees, είναι το σημαντικότερο ανοικτό πρόβλημα στην περιοχή των άμεσων αλγορίθμων.

Στις πτυχιακές και διπλωματικές εργασίες θα μελετήσουμε τις βασικές δημοσιεύσεις, θα γράψουμε μια επισκόπηση, και θα πειραματιστούμε με περιπτώσεις του προβλήματος. Σκοπός των υπολογιστικών πειραμάτων θα είναι να:

- Να αποτιμήσουμε τη συμπεριφορά του Work Function Algorithm, ενός φυσικού άμεσου αλγόριθμου, για 3 servers και μακριές ακολουθίες αιτήσεων.

- Να προσπαθήσουμε να καταρρίψουμε την εικασία για προβλήματα με 3 servers και πολλές αιτήσεις. Να κατασκευάσουμε ένα πρόγραμμα που να ελέγχει την ορθότητα της εικασίας για ακολουθίες αιτήσεων συγκεκριμένου μεγέθους.

Πηγές:

Βιβλία:

Δημοσιεύσεις:

Ιστός:

2005.10.14-13:31.00
/Topics For Theses | 0 writebacks | permanent link

Πρόβλημα Πλανόδιου Πωλητή - Φράγμα Held-Karp

Ένα απο τα κεντρικά και ίσως το πιο γνωστό πρόβλημα βελτιστοποίησης είναι το Πρόβλημα του Πλανόδιου Πωλητή: Σ’ αυτό μας δίνονται οι αποστάσεις μεταξύ n πόλεων και μας ζητείται να βρούμε τη μικρότερη κλειστή διαδρομή που περνά από όλες τις πόλεις. Στην πιο ενδιαφέρουσα μορφή του προβλήματος, οι αποστάσεις ικανοποιούν την τριγωνική ανισότητα και μ’ αυτή την περίπτωση θα ασχοληθούμε εδώ. Το πρόβλημα είναι γνωστό ότι είναι NP-complete.

Ένα από τα πιο επίμονα ανοιχτά προβλήματα (από τις αρχές της δεκαετίας του ‘70) είναι να βρεθεί αλγόριθμος πολυωνυμικού χρόνου που βρίσκει μια λύση που μπορεί να μην είναι μεν βέλτιστη άλλα είναι κοντά σε αυτή, π.χ. το κόστος της λύσης να είναι το πολύ 30% μεγαλύτερο απο το βέλτιστο κόστος (σε αυτή τη περίπτωση, λέμε ότι η λύση έχει προσεγγιστικό λόγο 1.30). Ο αλγόριθμος του Χριστοφίδη (1975) βρίσκει λύσεις με προσεγγιστικό λόγο 1.5. Μπορούμε να βρούμε καλύτερο αλγόριθμο? Αυτό είναι ένα απο τα πιο σημαντικά αλγοριθμικά προβλήματα σήμερα.

Η απάντηση πιστεύεται γενικά ότι είναι θετική και ότι υπάρχει αλγόριθμος με λόγο προσέγγισης 4/3. Σχετικό με αυτό το λόγο είναι και το φράγμα Held-Karp. Το φράγμα είναι ο λόγος προσέγγισης που δίνει ένα πολύ φυσικό γραμμικό πρόγραμμα σχετικό με το TSP. Απο το 1970 υπάρχει η εικασία ότι το φράγμα Held-Karp είναι ίσο με 4/3, αλλά δεν μπορούμε να την αποδείξουμε ούτε να την καταρρίψουμε.

Στις πτυχιακές και διπλωματικές εργασίες θα μελετήσουμε τις βασικές δημοσιεύσεις, θα γράψουμε μια επισκόπηση, και θα πειραματιστούμε με περιπτώσεις του προβλήματος με μικρό αριθμό πόλεων (κάπου 10 πόλεις) για να προσδιορίσουμε το φράγμα Held-Karp. Σκοπός των υπολογιστικών πειραμάτων θα είναι να:

- Να βρεθεί το φράγμα Held-Karp για n πόλεις, όπου n=6,7,…,12

- Να χαρακτηριστούν οι λύσεις του φράγματος Held-Karp (π.χ. στις μη ακέραιες λύσεις, πόσο μεγάλοι είναι οι παρονομαστές των κλασμάτων;).

- Να διαμορφωθούν εικασίες για το πως μπορεί να μετατραπεί με αποδοτικό τρόπο μια κλασματική λύση του φράγματος Held-Karp σε ακέραια, και να ελεγχθούν για μικρό αριθμό πόλεων.

Πηγές:

Βιβλία:

Δημοσιεύσεις:

Ιστός:

2005.10.14-13:28.00
/Topics For Theses | 0 writebacks | permanent link

Τα άρθρα για τα μαθήματα δεν εμφανίζονται αυτόματα. Για να δείτε τα άρθρα για κάποιο μάθημα, επιλέξτε από το μενού Classes.

Αν χρησιμοποιειτε RSS για να δειτε τα αρθρα καποιας ταξης, επιλεξτε πρωτα απο το μενου την καταλληλη ταξη και μετα χρησιμοποιειστε το url απο το “Subscribe” στο δεξιο μερος. Π.χ. για την ταξη Game Theory το url ειναι
http://www.di.uoa.gr/~elias/index/Classes/Game%20Theory/index.html
ενω το RSS feed ειναι
http://www.di.uoa.gr/~elias/index/Classes/Game%20Theory/index.rss.

2005.02.22-12:05.00
| 0 writebacks | permanent link

This is my weblog and personal web page together. My main aim is to include information about my research and teaching at the University of Athens. Computer Science theorists do not seem to maintain weblogs (yet). I know only of Lance Fortnow’s weblog.

You can use the menu on the left to navigate and select topics. Especially for classes, the entries do not appear automatically. To see them, please select from the menu “Classes” or search.

The see only the entries in english click on the british flag on the upper-right corner. If you want to see all entries, you need to click on the greek flag .

You can subscribe to an RSS feed of this site, or even a feed of a topic. Select first the topic for the menu on the left—if you want all articles click on the top banner. Then use the subscribe link on the right side of the page or use the live bookmark features of your browser. For example to subscribe to all articles use this link
http://www.di.uoa.gr/~elias/index/index.rss?language=2
To subscribe to all articles about classes use this link
http://www.di.uoa.gr/~elias/index/Classes/index.rss?language=2

If you want to express your opinion about an article or to see the comments of others, please click on the writeback link at the end of the article. To avoid spam you have to verify that you belong to the homo sapiens spieces. Make sure that you verify this fact when you are asked to, otherwise your message will be lost.
Quiz: My method seems to defeat bots (at least for now). Can you see how?

The weblog is powered by blosxom, a cool perl script enhanced by scripts from the blosxom community.

2005.02.22-12:03.00
/About This Site | 1 writeback | permanent link

With George Christodoulou, we considered the price of anarchy of pure Nash equilibria in congestion games with linear latency functions. We showed that for general (asymmetric) games, the price of anarchy of maximum social cost is \Theta(\sqrt{N}), where N is the number of players. For all other cases of symmetric or asymmetric games and for both maximum and average social cost, the price of anarchy is 5/2.

The paper CK05 will appear in STOC 2005. Similar results, for the case of total latency cost function, were obtained by Awerbuch, Azar, and Epstein. Their paper will also appear in STOC 2005.

2005.02.14-15:33.00
/Research/Game Theory | 0 writebacks | permanent link

With George Christodoulou, we considered the price of stability, which is the optimistic price of anarchy (the ratio of the best equilibrium over the optimal allocation), for Nash and correlated equilibria. We showed that for linear congestion games the price of stability is between 1.577 and 1.6 for dominant strategies, Nash, and correlated equilibria. This holds for the average (sum) social cost. For the max social cost, the price of stability is \Theta(\sqrt{N}), where N is the number of players.

The results can be found in CK05b (submitted to ICALP’05). In the same paper, we extended some of the results of our STOC 05 (and also of the STOC’05 paper of Awerbuch, Azar, Epstein) to correlated equilibria.

2005.02.14-15:32.00
/Research/Game Theory | 0 writebacks | permanent link

Ο νέος θεσμός συμβούλου για τους φοιτητές του τμήματός μας μπορεί να λύσει πολλά προβλήματα αλλά για να πετύχει χρειάζεται τη συμμετοχή όλων, φοιτητών και συμβούλων. Είναι ευκαιρία τουλάχιστον σε αυτή τη φάση να καταγραφούν προβλήματα και προβληματισμοί αλλά και θετικές εμπειρίες. Κάποια από τα προβλήματα μπορεί να μην έχουν άμεση λύση ή να μην μπορούμε να τα λύσουμε καθόλου. Κάποια άλλα μπορεί να λυθούν άμεσα.

Από την άλλη, ίσως αυτή να είναι μια καλή ευκαιρία να δούμε κάποια θέματα πιο σφαιρικά και να διαλυθούν έτσι κάποιες λανθασμένες εντυπώσεις. Θα αναφερθώ σε 3-4 τέτοια θέματα που έτυχε να ακούσω.

See more ...

2004.12.16-07:25.00
/Student Issues | 8 writebacks | permanent link

An interesting book (in English) about mountainous Greece. Tim Salmon is a British teacher who has lived in Greece for many years and traveled a lot in the Agrafa region and around the vlach village of Samarina. He describes his encounters and, through them, he attempts to analyze the identity of modern Greece. Here is an extensive review.

2004.08.09-19:54.00
/Random Thoughts | 0 writebacks | permanent link

New York Times has an interesting collection of photos from Magnum Photos about the Olympics and Greece in general.

Since the subject is photos and Magnum, I should mention two collection of photos from Greece by the recently deceased Henri Cartier-Bresson: Greece 1953 and Greece 1961.

2004.08.06-16:41.00
/Random Thoughts | 0 writebacks | permanent link

A weblog is essentially an online diary. The author of the weblog posts articles called blogs on a web page. This is done usually in reverse chronological order.

Many weblog sites allow readers to write comments or replies on weblogs. These are called writebacks. You can read the writebacks to my postings or add a writeback by folowing the appropriate link at the end of my postings.

A similar concept is trackbacks. In this case readers post replies on their own weblog not on the original weblog. To connect a reply with the original weblog they leave a trackback. In other words, trackbacks are similar to short writebacks of the form “a reply to this blog has been posted on site …”.

As a weblog evolves, it is useful to have a fixed reference to each blog that does change over time. These are called permanent links.

2004.06.05-23:10.00
/About This Site | 0 writebacks | permanent link

Blosxom is a perl script for publishing weblogs. It is very extendable by many useful plugins written by the blosxom community —some of them employed in this website.

The author writes the weblongs as text or html files and blosxom creates the web pages automatically. One of its nice features is that the author can maintain the weblogs in a directory tree which reflects the categories or topics.

You can find more about blosxom on its website.

2004.06.05-22:56.00
/About This Site | 0 writebacks | permanent link

Here is a list of my publications from my old personal page—until I populate this weblog with references to these papers.

2004.05.11-10:09.00
/Research/Publications | 0 writebacks | permanent link

In a system with selfish users, the system may run at suboptimality. In CKN04, we propose coordination mechanisms as a way to improve the performance. Coordination mechanisms bring together online algorithms and the price of anarchy in a nice framework with challenging problems.

I also wrote a simple exposition article on the topic in the Bulletin of EATCS which I expanded for the SIGACT News.

2004.05.11-09:23.00
/Research/Game Theory | 0 writebacks | permanent link

The k-server problem is the central problem in the area of online algorithms. In my PhD thesis Kou94 and together with my friend and advisor Christos Papadimitriou KP95, we showed that the Work Function Algorithm has competitive ratio 2k-1; the previous bound, showed by Fiat-Rabani-Ravid and by Grove-Bartal, was exponential in k. Ten years later (as of this writing), the bound 2k-1 is still the best known. The k-server conjecture which states that there is a k-competitive algorithm remains the most challenging problem in the area of online algorithms.

I published a simpler proof of the 2k-1 bound in Kou99. I also published two more papers on the topic: in KP96 we proved the k-server conjecture for metric spaces of k+2 points and in BK04 we proved the conjecture for a few more special cases of metric spaces (line and weighted star).

2004.05.10-23:15.00
/Research/Online Algorithms | 2 writebacks | permanent link

In the paper KP99 with Christos Papadimitriou, we study the degradation in performance due to selfish behavior of the users. The paper is not technically deep but it raised an important question and had a huge impact. Together with a few other pioneering papers, such as Ronen and Nisan’s work on mechanism design, it opened up a beautiful new field in the intersection of Computer Science and Game Theory.

In this paper we view users as players in a non-cooperative game that play at the worst-case Nash equilibrium and compare with the optimal allocation. We initially called this the coordination ratio of the system (to relate it with the competitive ratio and approximation ratio); later Christos Papadimitriou called it the price of anarchy, and the latter term stuck.

In the paper we show that the price of anarchy for 2 facilities (machines, links) is exactly 3/2 and gave weak bounds for more facilities. In a later paper KMS03 with Marios Mavronikolas and Paul Spirakis, we showed tight bounds. Independently, Czumaj and Voecking proved a similar result but greatly expanded it to non-uniform facilities (see a nice review article by Czumaj).

2004.05.10-21:43.00
/Research/Game Theory | 0 writebacks | permanent link

I discovered that RSS and news aggregators are cool ideas. I downloaded Freereader, a free aggregator for W2K.

Reuters now supports RSS. On its site there is a nice short explanation about RSS.

You can even subscribe to a syndicated feed of this weblog by clicking on the sidebar.

2004.04.28-18:27.00
/Random Thoughts | 0 writebacks | permanent link

This is my first weblog. I still don’t know my intended readership and for the moment I am writing it for myself alone.

2004.04.28-18:27.00
/Random Thoughts | 0 writebacks | permanent link