Clustering, weighted sequences, and shortest paths

Abstract

In this thesis we focus on clustering problems where the input is the ideal relationship between all pairs of objects in the final clustering. More particularly, we concern ourselves with the following problems.Ll-fitting tree metrics and ultrametrics: We are given the ideal distance between all pairs of n objects, and the goal is to output a weighted tree (resp. ultrametric) which spans the set of objects and minimizes the sum of pairwise distance errors. Both problems are closely related to evolutionary biology and the reconstruction of the tree of life. In fact, discussions related to the reconstruction of the optimal tree are traced back to Plato and Aristotle (350 BC), in the context of classification. Both problems were known to be APX-Hard and the best known approximation factor was O((logn)(loglogn)) by Ailon and Charikar [FOCS '05]. We design asymptotically optimal constant factor approximations for both problems. Our paper "Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor" appeared in FOCS '21.Constrained Correlation Clustering: For each pair of objects, we are given a preference related to whether the two objects should be in the same cluster or not. Furthermore, we are also given hard constraints for certain pairs. The output clustering must satisfy all hard constraint, and minimize the number of violated preferences.We design a deterministic combinatorial algorithm with a constant approximation factor. A key ingredient in our approach is a novel nearly-optimal pivoting algorithm for Correlation Clustering. This is a deterministic combinatorial algorithm achieving the best approximation factor among all known deterministic combinatorial algorithms for Correlation Clustering, not just pivoting ones. Part of these results have been submitted to ICALP.Apart from clustering, we also study graph and string problems.Multiple Source Shortest Paths in Planar Graphs: Given an embedded planar digraph with positive edge weights and a face f, we are interested in a data structure supporting shortest path queries, where the source is in f. The best known data structure by Klein [SODA '05] requires O(nlogn) time for preprocessing and O(logn) time for queries, where n is the number of nodes. We improve the preprocessing/query time to O(nlog lfl )/O(log lfl ), where lfl is the number of nodes in f. More importantly, our approach is much simpler, requiring only single source shortest path computations and contractions. In contrast, Klein's solution required persistency, dynamic trees, and an interplay between the primal and the dual graph. Our paper "A Simple Algorithm for Multiple Source Shortest Paths in Planar Digraphs" appeared in SOSA '22.Longest Common Subsequence on Weighted Sequences: Weighted sequences generalize the concept of strings, so that in each position we have a probability distribution over the alphabet, rather than a single character. The motivation comes from the inherent uncertainty of the actual methods used for "reading" a DNA sequence. We suggest that the alphabet size is a crucial parameter for this problem, and provide optimal results both in the case of bounded and unbounded alphabets. Furthermore, this is the first work on Weighted Sequences avoiding the Log-Probability model, a simplifying assumption related to exact computations of reals. Our paper "Longest Common Subsequence on Weighted Sequences" received the Best Paper Award at CPM '20.

Σε αυτή τη διατριβή εστιάζουμε σε προβλήματα συσταδοποίησης όπου η είσοδος είναι η ιδανική σχέση μεταξύ όλων των ζευγών αντικειμένων στην τελική συσταδοποίηση. Πιο συγκεκριμένα, ασχολούμαστε με τα ακόλουθα προβλήματα.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.