Facets for Art Gallery Problems
Facets for Art Gallery Problems
复制标题
美术馆问题的各个方面
DOI：
10.1007/s00453-014-9961-x
复制
发表时间：
2015
期刊：
影响因子：
1.1
通讯作者：
Christiane Schmidt
中科院分区：
文献类型：
--
作者：
Sándor P. Fekete;Stephan Friedrichs;Alexander Kröller;Christiane Schmidt
美术馆问题（AGP）要求在多边形区域中放置最少数量的固定警卫，使得区域中的所有点都有警卫。这个问题是NP-难的，其固有的连续结构（需要保护的点集和可以用于保护的点集都是不可数的无限）使得很难将简单的公式化为整数线性规划。我们使用一个迭代的原始-对偶松弛方法来解决AGP实例的最优性。在每个阶段，一对LP松弛的原始覆盖和对偶包装约束和变量的一个有限的候选子集被认为是这些对应于可能的保护位置和点被保护。特别有用的是用于消除分数解的切割平面。我们确定了两类方面，基于边覆盖和集覆盖（SC）的不平等。解决后者的分离问题是NP完全的，但利用底层的几何结构，我们表明，大子类的分数SC解决方案不能发生的AGP。这允许我们在多项式时间内分离相关的面子集。我们还描述了所有方面的有限AGP松弛系数。最后，我们证明了我们的方法的实际用途。与Kröller等人的方法相比，我们的切割平面技术在速度和解决方案质量方面产生了显着的改进，这是由于大大减少了完整性差距（ACM J Exp Algorithm 17（1）：2.3：2.1-2.3：2.23，2012）。
TheArt Gallery Problem(AGP) asks for placing a minimum number of stationary guards in a polygonal region, such that all points inare guarded. The problem is known to be NP-hard, and its inherent continuous structure (with both the set of points that need to be guarded and the set of points that can be used for guarding being uncountably infinite) makes it difficult to apply a straightforward formulation as an integer linear program. We use an iterative primal-dual relaxation approach for solving AGP instances to optimality. At each stage, a pair of LP relaxations for a finite candidate subset of primal covering and dual packing constraints and variables is considered; these correspond to possible guard positions and points that are to be guarded. Particularly useful are cutting planes for eliminating fractional solutions. We identify two classes of facets, based onEdge CoverandSet Cover(SC) inequalities. Solving the separation problem for the latter is NP-complete, but exploiting the underlying geometric structure, we show that large subclasses of fractional SC solutions cannot occur for the AGP. This allows us to separate the relevant subset of facets in polynomial time. We also characterize all facets for finite AGP relaxations with coefficients in. Finally, we demonstrate the practical usefulness of our approach. Our cutting plane technique yields a significant improvement in terms of speed and solution quality due to considerably reduced integrality gaps as compared to the approach by Kröller et al. (ACM J Exp Algorithm 17(1): 2.3:2.1–2.3:2.23, 2012).
登录
查看更多内容
DOI：
--
发表时间：
2010
期刊：
Workshop on Algorithms and Computation
影响因子：
--
作者：
S. Ghosh
通讯作者：
S. Ghosh
控球后卫和点云：解决一般美术馆问题
DOI：
--
发表时间：
2013
期刊：
International Symposium on Computational Geometry
影响因子：
--
作者：
D. Borrmann;P. J. Rezende;C. C. Souza;S. Fekete;Stephan Friedrichs;A. Kröller;A. Nüchter;Christiane Schmidt;Davi C. Tozoni
通讯作者：
Davi C. Tozoni
寻求美术馆问题的最佳解决方案：一种实用的迭代算法
DOI：
--
发表时间：
2013
期刊：
The Sea
影响因子：
--
作者：
Davi C. Tozoni;P. J. Rezende;C. C. Souza
通讯作者：
C. C. Souza
DOI：
--
发表时间：
2007
期刊：
SIBGRAPI Conference on Graphics, Patterns and Images
影响因子：
--
作者：
Marcelo C. Couto;C. C. Souza;P. J. Rezende
通讯作者：
P. J. Rezende
影响因子：
2.7
作者：
E. Balas;S. Ng
通讯作者：
S. Ng