Clustering, weighted sequences, and shortest paths
Authors: Κηπουρίδης Ευάγγελος 
Published: February 2023

Σε αυτή τη διατριβή εστιάζουμε σε προβλήματα συσταδοποίησης όπου η είσοδος είναι η ιδανική σχέση μεταξύ όλων των ζευγών αντικειμένων στην τελική συσταδοποίηση. Πιο συγκεκριμένα, ασχολούμαστε με τα ακόλουθα προβλήματα.L1-προσαρμογή μετρικών δέντρων και έξτρα-μετρικών: Μας δίνεται η ιδανική απόσταση μεταξύ όλων των ζευγών n αντικειμένων και ο στόχος είναι να εξάγουμε ένα βεβαρυμένο δέντρο (αντίστοιχα έξτρα-μετρική) το οποίο καλύπτει το σύνολο των αντικειμένων και ελαχιστοποιεί το άθροισμα των σφαλμάτων απόστασης ανά ζεύγη. Και τα δύο προβλήματα σχετίζονται στενά με την εξελικτική βιολογία και την ανακατασκευή του δέντρου της ζωής. Μάλιστα εντοπίζουμε συζητήσεις που σχετίζονται με την ανακατασκευή του βέλτιστου δέντρου από τον Πλάτωνα και τον Αριστοτέλη (350 π.Χ.), στο πλαίσιο του προβλήματος της κατάταξης. Και τα δύο προβλήματα ήταν γνωστό ότι είναι APX-Hard και ο καλύτερος γνωστός παράγοντας προσέγγισης ήταν O((logn)(loglogn)) από τους Ailon και Charikar [FOCS '05]. Σχεδιάζουμε ασυμπτωτικά βέλτιστες προσεγγίσεις σταθερού παράγοντα και για τα δύο προβλήματα. Η εργασία μας "Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor" δημοσιεύτηκε στο FOCS '21.Συσταδοποίηση Συσχέτισης με περιορισμούς: Για κάθε ζεύγος αντικειμένων, μας δίνεται μια προτίμηση που σχετίζεται με το αν τα δύο αντικείμενα πρέπει να βρίσκονται στην ίδια συστάδα ή όχι. Επιπλέον, μας δίνονται και περιορισμοί για ορισμένα ζεύγη. Η ομαδοποίηση εξόδου πρέπει να ικανοποιεί όλους τους περιορισμούς και να ελαχιστοποιεί τον αριθμό των παραβιασμένων προτιμήσεων.Σχεδιάζουμε έναν ντετερμινιστικό συνδυαστικό αλγόριθμο με σταθερό παράγοντα προσέγγισης. Βασικό συστατικό της προσέγγισής μας είναι ένας νέος σχεδόν-βέλτιστος αλγόριθμος pivoting για τη Συσταδοποίηση Συσχέτισης. Πρόκειται για έναν ντετερμινιστικό συνδυαστικό αλγόριθμο που επιτυγχάνει τον καλύτερο παράγοντα προσέγγισης μεταξύ όλων των γνωστών ντετερμινιστικών συνδυαστικών αλγορίθμων για την Συσταδοποίηση Συσχέτισης, όχι μόνο των αλγορίθμων τύπου pivoting. Μέρος αυτών των αποτελεσμάτων έχει υποβληθεί στο ICALP.Εκτός από τη συσταδοποίηση, μελετάμε επίσης προβλήματα γραφημάτων και συμβολοσειρών.Πολλαπλών πηγών συντομότερα μονοπάτια σε επίπεδους γράφους: Δεδομένου ενός ενσωματωμένου επίπεδου κατευθυνόμενου γράφου με θετικά βάρη ακμών και μια όψη f, ενδιαφερόμαστε για μια δομή δεδομένων που υποστηρίζει ερωτήματα συντομότερων μονοπατιών, όπου η πηγή βρίσκεται στην f. Η καλύτερη γνωστή δομή δεδομένων από τον Klein [SODA '05] απαιτεί O(nlogn) χρόνο για προεπεξεργασία και O(logn) χρόνο για ερωτήματα, όπου n είναι ο αριθμός των κόμβων. Βελτιώνουμε τον χρόνο προεπεξεργασίας/ερωτημάτων σε O(nlog lfl )/O(log lfl ), όπου lfl είναι ο αριθμός των κόμβων στο f. Το πιο σημαντικό είναι ότι η προσέγγισή μας είναι πολύ απλούστερη, και απαιτεί μόνο υπολογισμούς συντομότερου μονοπατιού μίας πηγής και συστολές. Αντίθετα, η λύση του Klein απαιτούσε μονιμότητα, δυναμικά δέντρα και μια αλληλεπίδραση μεταξύ του πρωταρχικού και του δυαδικού γράφου. Η εργασία μας "A Simple Algorithm for Multiple Source Shortest Paths in Planar Digraphs" δημοσιεύτηκε στο SOSA '22.Μακρύτερη κοινή ακολουθία σε ζυγισμένες ακολουθίες: Οι ζυγισμένες ακολουθίες γενικεύουν την έννοια των συμβολοσειρών, έτσι ώστε σε κάθε θέση να έχουμε μια κατανομή πιθανοτήτων πάνω στο αλφάβητο, αντί για έναν μεμονωμένο χαρακτήρα. Το κίνητρο προέρχεται από την εγγενή αβεβαιότητα των πραγματικών μεθόδων που χρησιμοποιούνται για την "ανάγνωση" μιας ακολουθίας DNA. Προτείνουμε ότι το μέγεθος του αλφαβήτου είναι μια κρίσιμη παράμετρος για το πρόβλημα αυτό και παρέχουμε βέλτιστα αποτελέσματα τόσο στην περίπτωση των περιορισμένων όσο και των μη περιορισμένων αλφαβήτων. Επιπλέον, αυτή είναι η πρώτη εργασία σχετικά με τις ζυγισμένες ακολουθίες που αποφεύγει το μοντέλο Λογαριθμικής-Πιθανότητας, μια απλουστευτική υπόθεση που σχετίζεται με ακριβείς υπολογισμούς πραγματικών αριθμών. Η εργασία μας "Longest Common Subsequence on Weighted Sequences" έλαβε το βραβείο καλύτερης εργασίας στο CPM '20.