Ανάλυση απόδοσης άμεσων αλγόριθμων για ευσταθείς εισόδους προβλημάτων ομαδοποίησης - Βαλκάνος, Γεώργιος (Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών, 2018)
Η ανάγκη να επιλύουμε γρήγορα και με τον καλύτερο δυνατό τρόπο τα αλγοριθμικά μας προβλήματα έχει οδηγήσει τους ερευνητές σε νέες τεχνικές και μεθόδους. Η πιο ενδιαφέρουσα από αυτές στηρίζεται στην μελέτη και κατασκευή αλγόριθμων που αντιμετωπίζουν μόνο τις εισόδους με τις οποίες έρχεται αντιμέτωπο το πρόβλημα. Μιλάμε, δηλαδή, για μια ανάλυση πέρα της χειρότερης περίπτωσης που εστιάζει στην μελέτη και αξιοποίηση των χαρακτηριστικών των καλών εισόδων. Στα πλαίσια αυτής της διπλωματικής παρουσιάζουμε δουλειά προγενέστερων πάνω σε προβλήματα ομαδοποίησης. Δείχνουμε, ότι κάτω από λογικές συνθήκες που πρέπει να διέπουν μια πραγματική είσοδο μπορούμε να επιλύσουμε το πρόβλημα k-median σε πολυωνυμικό χρόνο. Συγκεκριμένα, παρουσιάζουμε δύο κλάσεις εισόδων, αυτές που είναι σταθερές στις προσεγγίσεις και αυτές που είναι ανθεκτικές στις διαταραχές. Στη συνέχεια, μελετάμε το πρόβλημα της online τοποθέτησης εργοστασίων και κάνουμε αναφορά σε δύο 2 γνωστούς αλγορίθμους. Τέλος, εισάγουμε για πρώτη φορά την έννοια της ανθεκτικής στις διαταραχές εισόδου σε πρόβλημα online ομαδοποίησης και συγκεκριμένα στο πρόβλημα της online τοποθέτησης εργοστασίων. Δείχνουμε, πως η γεωμετρία της εισόδου μπορεί να μας ωφελήσει ακόμη και όταν δεν γνωρίζουμε ολόκληρη την είσοδο. Παίρνουμε έναν γνωστό αλγόριθμο για το πρόβλημα και απλοποιούμε την ανάλυση του για ανθεκτικές εισόδους. Δείχνουμε ότι χρειάζεται σταθερός αριθμός εργοστασίων για να ανεξαρτητοποιηθούν δύο ομάδες τις βέλτιστης λύσης, ώστε να μπορούν να μελετηθούν ξεχωριστά.