Optimal facility location problem on polyhedral terrains using descending paths

Autor: Binayak Dutta, Sasanka Roy, Arindam Karmakar
Rok vydání: 2020
Předmět:
Zdroj: Theoretical Computer Science. 847:68-75
ISSN: 0304-3975
Popis: We study the descending facility location (DFL) problem on the surface of a triangulated terrain. A path from a point s to a point t on the surface of a terrain is descending if the heights of the subsequent points along the path from s to t are in a monotonically non-increasing order [1] . We are given a set D = { d 1 , d 2 , ⋯ , d n } of n demand points on the surface of a triangulated terrain W and our objective is to find a set F (of points), of minimum cardinality, on the surface of the terrain such that for each demand point d ∈ D there exists a descending path from at least one facility f ∈ F to d. We present an O ( ( n + m ) log ⁡ m ) time algorithm for solving the DFL problem, where m is the number of vertices in the triangulated terrain. We achieve this by reducing the DFL problem to a graph problem called the directed tree covering ( D T C ) problem. In the DTC problem, we have a directed tree B = ( V , E ) with a set of marked nodes M ⊆ V . The objective is to compute a set C ⊆ V of minimum cardinality, such that for every node v ∈ M , either v ∈ C or there exists a node c ∈ C such that v is reachable from c. We prove that the DFL problem can be reduced to DTC problem in O ( ( m + n ) log ⁡ m ) time. The DTC problem thereafter can be solved in O ( | V | ) time. We also prove that the general version of the DTC problem, called the directed graph covering ( D G C ) problem is NP-hard on directed bipartite graphs and hard to approximate within ( 1 − ϵ ) ln ⁡ | M | -factor, for every ϵ > 0 , where | M | is the size of the set of marked nodes. We also prove that for the DGC problem, an O ( log ⁡ | M | ) factor approximation is possible and this approximation factor is tight.
Databáze: OpenAIRE
Externí odkaz: