| 作成者 |
|
|
|
|
|
|
|
|
|
| 本文言語 |
|
| 出版者 |
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 開始ページ |
|
| 終了ページ |
|
| 会議情報 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 権利関係 |
|
| 権利関係 |
|
| 関連DOI |
|
| 関連DOI |
|
| 関連URI |
|
| 関連HDL |
|
| 関連ISBN |
|
| 関連HDL |
|
| 関連情報 |
|
| 概要 |
We study the approximability of the NP-complete Maximum Minimal Feedback Vertex Set problem. Informally, this natural problem seems to lie in an intermediate space between two more well-studied proble...ms of this type: Maximum Minimal Vertex Cover, for which the best achievable approximation ratio is √n, and Upper Dominating Set, which does not admit any n^<1-ε> approximation. We confirm and quantify this intuition by showing the first non-trivial polynomial time approximation for Max Min FVS with a ratio of O(n^<2/3>), as well as a matching hardness of approximation bound of n^<2/3-ε>, improving the previous known hardness of n^<1/2-ε>. Along the way, we also obtain an O(Δ)-approximation and show that this is asymptotically best possible, and we improve the bound for which the problem is NP-hard from Δ ≥ 9 to Δ ≥ 6.
Having settled the problem’s approximability in polynomial time, we move to the context of super-polynomial time. We devise a generalization of our approximation algorithm which, for any desired approximation ratio r, produces an r-approximate solution in time n^<O(n/r^<3/2>)>. This time-approximation trade-off is essentially tight: we show that under the ETH, for any ratio r and ε > 0, no algorithm can r-approximate this problem in time n^<O((n/r^<3/2>)^<1-ε>)>, hence we precisely characterize the approximability of the problem for the whole spectrum between polynomial and sub-exponential time, up to an arbitrarily small constant in the second exponent.続きを見る
|
Mendeley出力
