Αλγόριθμος του Manoj Gupta σπάει όριο από το 1996 στις συντομότερες διαδρομές

Ο δρ. Manoj Gupta, αναπληρωτής καθηγητής στο Indian Institute of Technology Gandhinagar, παρουσίασε στο 66ο ετήσιο Symposium on Foundations of Computer Science (FOCS 2025) αλγόριθμο που επεκτείνει την εγγύηση 2-προσέγγισης για κοντινά ζεύγη κόμβων, χωρίς να αυξάνει τον συνολικό χρόνο εκτέλεσης. Η εργασία τιτλοφορείται «Improved 2-Approximate Shortest Paths for close vertex pairs».

Το πρόβλημα είναι γνωστό ως All-Pairs Shortest Paths (APSP): ο υπολογισμός της συντομότερης απόστασης ανάμεσα σε κάθε ζεύγος σημείων ενός γράφου. Σε πυκνά δίκτυα, οι κλασικές μέθοδοι συχνά απαιτούν κυβικό χρόνο, με το υπολογιστικό κόστος να αυξάνεται ταχύτερα από το ίδιο το δίκτυο. Γι’ αυτό οι ερευνητές στράφηκαν σε προσεγγιστικούς αλγορίθμους, που δίνουν επαρκώς ακριβείς αποστάσεις με πολύ λιγότερη δουλειά.

Σημαντικό ορόσημο ήταν το 1996, όταν οι Dor, Halperin και Zwick (DHZ) πρότειναν μέθοδο που, σε σχεδόν βέλτιστο χρόνο, παρείχε εκτιμήσεις εντός του διπλάσιου της πραγματικής απόστασης για επαρκώς απομακρυσμένα ζεύγη σημείων. Η «2-προσέγγιση» σημαίνει πως, αν η ακριβής διαδρομή είναι 10 χιλιόμετρα, η εκτίμηση θα βρίσκεται μεταξύ 10 και 20.

Η προσέγγιση DHZ βασίστηκε σε επιλεγμένα «δειγματοληπτικά» σημεία του δικτύου, που λειτουργούν ως συντομεύσεις. Αυτό λειτουργεί καλά όταν τα σημεία είναι μακριά μεταξύ τους — μια διαδρομή τύπου Δελχί–Τσενάι επιτρέπει να βρεθεί δείγμα κοντά στη βέλτιστη πορεία. Όμως για κοντινές αποστάσεις, όπως μεταξύ συνοικιών στα προάστια της Βομβάης, τα δείγματα μπορεί να πέφτουν μακριά από την ευθεία σύνδεση και η εκτίμηση να ξεπερνά το «διπλάσιο», παραβιάζοντας την εγγύηση.

Το νέο αποτέλεσμα του Gupta αντιμετωπίζει ακριβώς αυτό το κενό. Με μια πολυκλιμακωτή στρατηγική δειγματοληψίας, οργανώνει την πληροφορία του δικτύου σε περισσότερα επίπεδα, ώστε να «βλέπει» και τις κοντύτερες διαδρομές που συχνά διαφεύγουν σε ένα μόνο επίπεδο δειγματοληψίας. Έτσι μειώνεται το ελάχιστο μήκος στο οποίο ισχύει η εγγύηση 2-προσέγγισης, χωρίς επιβάρυνση της υπολογιστικής πολυπλοκότητας.

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

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

Πηγή: share.google.