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

Abstract

The rapidly evolving telecommunication technologies are continuously creating new research fields of so much practical as well as theoretical interest. The always increasing reliability and independence of wireless communication networks are driving the communication service providers towards the complete replacement of the wired infrastructure. However, there is an enormous cost of investment in order to create and keep operational any wireless telecommunication network. In an abstract model, if two points can communicate using a communication station (i.e. an antenna), we say that the points are covered by the station. In order to cover every point of a geographical region we need to find the minimum number of stations that are necessary for the covering requirement. This is the classical minimization problem that is well known and studied, regarding its combinatorial and algorithmic aspects. A reasonable variation is to try to cover as many points as possible using a given number of stations. This variation takes into account that a given budget might not suffice for the total covering of the geographical region. Communication between two points might be possible or blocked and that depends on the area topology. Polygons with, or without holes, have been used as models. We present here a general greedy approach in order to deal with the maximization variations of the classical covering problem: there is a number of different guarding positions (vertices, edges) and k given guards of the appropriate type (vertex-guards, edge-guards). The problem is to find good positions for the guards in order to fulfill a covering requirement (complete or partial coverage) that maximizes a function (length, area, value, etc.) of the covered point sets. We also investigate the cases where the calculation of the function value is NP-hard and the cases where there are fixed costs in order to place guards and the total cost has to be within a given budget. For all these variations we prove that we have NP-hard problems and by applying the proposed greedy approach, we construct polynomial time approximation algorithms that achieve constant approximation ratios. We present also a gap preserving reduction from a well-known APX-hard problem to the problem of maximizing the covered length of the polygon’s boundary, using k vertex guards. The reduction holds, with more or less minor modifications, for all of the investigated maximization problems. We prove that, unless P=NP, no maximization problem admits a polynomial time approximation scheme: there exist constants that cannot occur as approximation ratios of any polynomial time approximation algorithm that solves any of the maximization problems.

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