Σχεδόν βέλτιστοι αλγόριθμοι και αποτελέσματα μη-προσέγγισης για προβλήματα κάλυψης πολυγωνικών περιοχών
Authors: Φραγκουδάκης Χριστόδουλος 
Published: August 2021

Οι ταχύτατα αναπτυσσόμενες τεχνολογίες τηλεπικοινωνιών δημιουργούν συνεχώς νέα πεδία έρευνας με πρακτικό αλλά και θεωρητικό ενδιαφέρον. Η αξιοπιστία και η ανεξαρτησία των ασυρμάτων δικτύων επικοινωνιών οδηγούν τους παρόχους υπηρεσιών δικτύωσης στην πλήρη αντικατάσταση των ενσύρματων υποδομών. Το κόστος όμως της επένδυσης που απαιτείται για τη δημιουργία και τη διατήρηση σε λειτουργία ενός ασυρμάτου δικτύου τηλεπικοινωνιών είναι τεράστιο. Σε ένα αφηρημένο μοντέλο, αν δύο σημεία επικοινωνούν μέσω ενός σταθμού επικοινωνίας (δηλαδή μιας κεραίας), τότε λέμε ότι τα σημεία καλύπτονται από το σταθμό. Για να καλυφθεί κάθε σημείο μιας γεωγραφικής περιοχής χρειάζεται να βρεθεί ο ελάχιστος αριθμός σταθμών που είναι απαραίτητοι για να ικανοποιηθούν οι απαιτήσεις της κάλυψης. Αυτό είναι το κλασικό πρόβλημα ελαχιστοποίησης που είναι καλά μελετημένο και από τη συνδυαστική και από την αλγοριθμική του σκοπιά. Μια ρεαλιστική παραλλαγή είναι η προσπάθεια κάλυψης όσο το δυνατό περισσότερων σημείων με χρήση ενός δεδομένου αριθμού σταθμών. Η παραλλαγή αυτή λαμβάνει υπόψη ότι ένα περιορισμένος προϋπολογισμός μπορεί να μην είναι αρκετός για την αγορά των σταθμών που χρειάζονται για την πλήρη κάλυψη της γεωγραφικής περιοχής. Η άμεση επικοινωνία μεταξύ δύο σημείων μπορεί να μην είναι εφικτή και αυτό εξαρτάται από την τοπολογία της περιοχής. Τα πολύγωνα με τρύπες, ή χωρίς τρύπες, έχουν χρησιμοποιηθεί σαν μοντέλα των γεωγραφικών περιοχών. Παρουσιάζουμε εδώ μια γενική άπληστη μέθοδο με σκοπό να αντιμετωπίσουμε τις παραλλαγές μεγιστοποίησης του κλασσικού προβλήματος κάλυψης: υπάρχει ένας αριθμός διαφορετικών θέσεων φύλαξης (κορυφές, ακμές) και k φύλακες του κατάλληλου τύπου (φύλακες-κορυφές, φύλακες-ακμές). Το πρόβλημα είναι να βρεθούν «καλές θέσεις» για τους φύλακες έτσι ώστε να υλοποιείται η απαίτηση της κάλυψης (πλήρης ή μερική κάλυψη) και να μεγιστοποιείται μια συνάρτηση (μήκος, εμβαδόν, αξία, κτλ.) που επιδρά στα καλυπτόμενα σύνολα σημείων. Διερευνούμε επίσης και τις περιπτώσεις όπου ο υπολογισμός και μόνο της τιμής της συνάρτησης είναι NP-hard και τις περιπτώσεις που υπάρχουν δεδομένα κόστη για την τοποθέτηση των φυλάκων και το συνολικό κόστος δεν μπορεί να υπερβεί ένα δεδομένο προϋπολογισμό. Αποδεικνύουμε ότι όλες αυτές οι παραλλαγές είναι NP-hard προβλήματα και με την εφαρμογή της άπληστης μεθόδου που προτείνουμε, κατασκευάζουμε πολυωνυμικού χρόνου προσεγγιστικούς αλγόριθμους που πετυχαίνουν σταθερούς προσεγγιστικούς λόγους. Παρουσιάζουμε επίσης και μια αναγωγή διατήρησης χάσματος από ένα γνωστό ΑΡΧ- hard πρόβλημα στο πρόβλημα μεγιστοποίησης του καλυπτόμενου μήκους στη περίμετρο με τη χρήση k φυλάκων-κορυφών. Η αναγωγή ισχύει με λιγότερες η περισσότερες τροποποιήσεις για όλα τα προβλήματα μεγιστοποίησης που εξετάσαμε. Αποδεικνύουμε ότι, εκτός αν Ρ=ΝΡ, δεν αποδέχεται κανένα πρόβλημα μεγιστοποίησης πολυωνυμικού χρόνου προσεγγιστικό σχήμα: υπάρχουν σταθερές που δεν μπορεί να είναι προσεγγιστικοί λόγοι οποιουδήποτε πολυωνυμικού χρόνου προσεγγιστικού αλγορίθμου που υπολογίζει λύσεις για οποιοδήποτε πρόβλημα μεγιστοποίησης.