Back to search

National Technical University of Athens (NTUA)

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

Abstract

dc:description

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.

Degree

thesis:*
Grantor dc:publisher
National Technical University of Athens (NTUA)
Year dc:date
2007

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Fragoudakis, Christodoulos
  • Φραγκουδάκης, Χριστόδουλος

Subjects

dc:subject × 12

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/16624

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Fragoudakis, Christodoulos; Φραγκουδάκης, Χριστόδουλος. Σχεδόν βέλτιστοι αλγόριθμοι και αποτελέσματα μη-προσέγγισης για προβλήματα κάλυψης πολυγωνικών περιοχών. National Technical University of Athens (NTUA), 2007. http://hdl.handle.net/10442/hedi/16624