| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2024-03-14 13:30 ［招待講演］Gap Amplification for Reconfiguration Problems ○Naoto Ohsaka（CyberAgent）  COMP2023-31 |
|
| 抄録 | （和） | (まだ登録されていません) |
| （英） | Combinatorial reconfiguration is an emerging field of theoretical computer science that studies the reachability between a pair of feasible solutions for a particular combinatorial problem. We study the hardness of accomplishing ``approximate'' reconfigurability, which affords to relax the feasibility of solutions. For example, in Minmax Set Cover Reconfiguration, given a pair of covers $mathcal{C}_mathsf{s}$ and $mathcal{C}_mathsf{t}$ for a set system $mathcal{F}$, we aim to transform $mathcal{C}_mathsf{s}$ into $mathcal{C}_mathsf{t}$ by repeatedly adding or removing a single set of $mathcal{F}$ so as to minimize the maximum size of covers during transformation. The recent study by Ohsaka (STACS 2023) gives evidence that a host of reconfiguration problems are PSPACE-hard to approximate assuming the Reconfiguration Inapproximability Hypothesis (RIH), which postulates that a gap version of Maxmin CSP Reconfiguration is PSPACE-hard. One limitation of this approach is that inapproximability factors are not explicitly shown, so that even a $1.00 cdots 001$-approximation algorithm for Minmax Set Cover Reconfiguration may not be ruled out, whereas it admits $2$-approximation as per Ito, Demaine, Harvey, Papadimitriou, Sideri, Uehara, and Uno (Theor. Comput. Sci., 2011). In this talk, we demonstrate gap amplification for reconfiguration problems. In particular, we prove an explicit factor of PSPACE-hardness of approximation for three popular reconfiguration problems only assuming RIH. Our main result is that under RIH, Maxmin Binary CSP Reconfiguration is PSPACE-hard to approximate within a factor of $0.9942$. Moreover, the same result holds even if the constraint graph is restricted to $(d,lambda)$-expander for arbitrarily small $frac{lambda}{d}$. The crux of its proof is an alteration of the gap amplification technique due to Dinur (J. ACM, 2007), which amplifies the $1$ vs. $1-epsilon$ gap for arbitrarily small $epsilon > 0$ up to the $1$ vs. $1-0.0058$ gap. As an application of the main result, we demonstrate that Minmax Set Cover Reconfiguration and Minmax Dominating Set Reconfiguration are PSPACE-hard to approximate within a factor of $1.0029$ under RIH. Our proof is based on a gap-preserving reduction from Label Cover to Set Cover due to Lund and Yannakakis (J. ACM, 1994). However, unlike Lund--Yannakakis' reduction, the expander mixing lemma is essential to use. We highlight that all results hold unconditionally as long as ``PSPACE-hard'' is replaced by ``NP-hard,'' and are the first explicit inapproximability results for reconfiguration problems without resorting to the parallel repetition theorem. We finally complement the main result by showing that it is NP-hard to approximate Maxmin Binary CSP Reconfiguration within a factor better than $frac{3}{4}$. |
|
| キーワード | （和） | / / / / / / / |
| （英） | combinatorial reconfiguration / hardness of approximation / gap amplification / / / / / | |
| 文献情報 | 信学技報, vol. 123, no. 444, COMP2023-31, pp. 22-22, 2024年3月. | |
| 資料番号 | COMP2023-31 | |
| 発行日 | 2024-03-07 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2023-31 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2024-03-14 - 2024-03-14 |
| 開催地（和） | 電気通信大学 |
| 開催地（英） | The University of Electro-Communications |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, etc |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2024-03-COMP |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Gap Amplification for Reconfiguration Problems |
| サブタイトル（英） | |
| キーワード(1)（和/英） | / combinatorial reconfiguration |
| キーワード(2)（和/英） | / hardness of approximation |
| キーワード(3)（和/英） | / gap amplification |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 大坂 直人 / Naoto Ohsaka / |
| 第1著者 所属（和/英） | 株式会社サイバーエージェント (略称： サイバーエージェント) CyberAgent, Inc. (略称： CyberAgent) |
| 講演者 | 第1著者 |
| 発表日時 | 2024-03-14 13:30:00 |
| 発表時間 | 60分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2023-31 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | no.444 |
| ページ範囲 | p.22 |
| ページ数 | 1 |
| 発行日 | 2024-03-07 (COMP) |
[研究会発表申込システムのトップページに戻る]