论文标题
压力下的概率P-CENTER问题的硬度和近似
Hardness and approximation of the Probabilistic p-Center problem under Pressure
论文作者
论文摘要
在压力下（Min PPCP）下的概率P-CENTER问题是我们最近在野火管理中引入的通常P-Center问题的变体。问题是要找到最小的P避难所，以最大程度地减少人们必须覆盖的最大距离，以便在发生火灾的情况下到达最接近的避难所。景观分为区域，并将其建模为边缘加权图，其顶点与对应于两个相邻区域之间的直接连接的区域和边缘相对应。与火灾爆发相关的风险是使用有限的火灾场景建模的。每种情况都对应于单个区域上的火爆发（即在顶点），其主要结果是通过两种方式修改疏散路径。首先，疏散路径不能穿过火上的顶点。其次，在选择逃脱方向时，接近火的人可能不会做出理性的决定，这一事实是使用新型撤离路径建模的。在本文中，对于由边缘加权图G =（V，E，L）和整数P定义的最小PPCP实例，我们表征了Min PPCP的一组可行解决方案。我们证明，最多3度的亚网格（网格亚段）的比率小于56/55，最多3。这些结果需要对（确定性）最小p-中心问题的两个变体的近似值结果，称为min mac p-center和min partial p-Center。
The Probabilistic p-Center problem under Pressure (Min PpCP) is a variant of the usual p-Center problem we recently introduced in the context of wildfire management. The problem is to locate p shelters minimizing the maximum distance people will have to cover to reach the closest accessible shelter in case of fire. The landscape is divided into zones and is modeled as an edge-weighted graph with vertices corresponding to zones and edges corresponding to direct connections between two adjacent zones. The risk associated with fire outbreaks is modeled using a finite set of fire scenarios. Each scenario corresponds to a fire outbreak on a single zone (i.e., on a vertex) with the main consequence of modifying evacuation paths in two ways. First, an evacuation path cannot pass through the vertex on fire. Second, the fact that someone close to the fire may not take rational decisions when selecting a direction to escape is modeled using new kinds of evacuation paths. In this paper, for a given instance of Min PpCP defined by an edge-weighted graph G=(V,E,L) and an integer p, we characterize the set of feasible solutions of Min PpCP. We prove that Min PpCP cannot be approximated with a ratio less than 56/55 on subgrids (subgraphs of grids) of degree at most 3. Then, we propose some approximation results for Min PpCP. These results require approximation results for two variants of the (deterministic) Min p-Center problem called Min MAC p-Center and Min Partial p-Center.
