Σχεδον Βελτιστοι Αλγοριθμοι Και Αποτελεσματα Μη Προσεγγισης Για Προβληματα Καλυψης Πολυγωνικων Περιοχων

Abstract

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