.png){kind=icon}
返回
Gap Amplification for Reconfiguration Problems
.png){kind=icon}
PRE
AI
DOI：10.1145/3779053.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
组合重构是一个全新领域，旨在研究组合问题解空间的连通性。我们研究了实现近似重构的难度，这允许放宽中间解的可行性。例如，在最小最大集合覆盖重构问题中，给定一个集合族及其两个覆盖，要求通过反复添加或删除该族中的一个集合，将一个覆盖转化为另一个覆盖，目标是最小化转换过程中遇到的覆盖的最大规模。Ohsaka（STACS 2023）的近期研究表明，在重构不可近似假设（RIH）下，若干重构问题是PSPACE-难的近似问题。该方法的局限性在于未明确展示不可近似因子，因此即使最小最大集合覆盖重构可能存在1.00...001近似算法也无法排除，而Ito、Demaine、Harvey、Papadimitriou、Sideri、Uehara和Uno（TCS 2011）已证明其存在2倍近似算法。本文中，我们证明了重构问题的间隙放大。具体而言，我们证明了在仅假设RIH的情况下，三个重构问题的近似因子具有明确的PSPACE-难度。我们的主要结果是，在RIH下，最小最大2-CSP重构问题近似因子0.9942是PSPACE-难的。其证明的关键在于对Dinur（JACM 2007）提出的间隙放大技术的改进，该技术将1 vs. 1-δ间隙提升至1 vs. 1-0.0058间隙，适用于任意小的正实数δ。作为主要结果的应用，我们进一步证明，在RIH下，最小最大集合覆盖重构和最小最大支配集重构近似因子1.0029是PSPACE-难的。
Keyword:
Reconfiguration Problems
Hardness of Approximation
Probabilistic Proof Systems
PSPACE-hardness
