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

Περίληψη

Οι ταχύτατα αναπτυσσόμενες τεχνολογίες τηλεπικοινωνιών δημιουργούν συνεχώς νέα πεδία έρευνας με πρακτικό αλλά και θεωρητικό ενδιαφέρον. Η αξιοπιστία και η ανεξαρτησία των ασυρμάτων δικτύων επικοινωνιών οδηγούν τους παρόχους υπηρεσιών δικτύωσης στην πλήρη αντικατάσταση των ενσύρματων υποδομών. Το κόστος όμως της επένδυσης που απαιτείται για τη δημιουργία και τη διατήρηση σε λειτουργία ενός ασυρμάτου δικτύου τηλεπικοινωνιών είναι τεράστιο. Σε ένα αφηρημένο μοντέλο, αν δύο σημεία επικοινωνούν μέσω ενός σταθμού επικοινωνίας (δηλαδή μιας κεραίας), τότε λέμε ότι τα σημεία καλύπτονται από το σταθμό. Για να καλυφθεί κάθε σημείο μιας γεωγραφικής περιοχής χρειάζεται να βρεθεί ο ελάχιστος αριθμός σταθμών που είναι απαραίτητοι για να ικανοποιηθούν οι απαιτήσεις της κάλυψης. Αυτό είναι το κλασικό πρόβλημα ελαχιστοποίησης που είναι καλά μελετημένο και από τη συνδυαστική και από την αλγοριθμική του σκοπιά. Μια ρεαλιστική παραλλαγή είναι η προσπάθεια κάλυψης όσο το δυνατό περισσότερων σημείων με χρήση ...
περισσότερα

Περίληψη σε άλλη γλώσσα

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 ...
περισσότερα
Πρέπει να είστε εγγεγραμένος χρήστης για έχετε πρόσβαση σε όλες τις υπηρεσίες του ΕΑΔΔ  Είσοδος /Εγγραφή

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/16624
ND
16624
Εναλλακτικός τίτλος
Near optimal algorithms and in-approximability results for art gallery problems
Συγγραφέας
Φραγκουδάκης, Χριστόδουλος Γεώργιος
Ημερομηνία
2007
Ίδρυμα
Εθνικό Μετσόβιο Πολυτεχνείο (ΕΜΠ). Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών. Εργαστήριο Υπολογιστικών Συστημάτων
Εξεταστική επιτροπή
Ζάχος Ευστάθιος
Αφράτη Φώτο
Σταφυλοπάτης Ανδρέας
Εμίρης Ιωάννης
Παπαιωάννου Αλέξανδρος
Παπασπύρου Νικόλαος
Παγουρτζής Αριστείδης
Επιστημονικό πεδίο
Μηχανική & Τεχνολογία
Επιστήμες Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού & Μηχανικού Η/Υ
Λέξεις-κλειδιά
Υπολογιστική γεωμετρία; Αλγόριθμοι προσέγγισης; Ορατότητα; Θεωρήματα φύλαξης μουσείου
Χώρα
Ελλάδα
Γλώσσα
Ελληνικά
Άλλα στοιχεία
110 σ., εικ., ευρ.