WEKO3
アイテム
Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems
http://hdl.handle.net/10228/0002000053
http://hdl.handle.net/10228/00020000537fa0f9c7-9f3b-4d7c-a20f-370590a459b8
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
10315887.pdf (241 KB)
|
|
| Item type | 学術雑誌論文 = Journal Article(1) | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-08-10 | |||||||||||||||||||||
| 資源タイプ | ||||||||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||||||||||
| 資源タイプ | journal article | |||||||||||||||||||||
| タイトル | ||||||||||||||||||||||
| タイトル | Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems | |||||||||||||||||||||
| 言語 | en | |||||||||||||||||||||
| 言語 | ||||||||||||||||||||||
| 言語 | eng | |||||||||||||||||||||
| 著者 |
Asahiro, Yuichi
× Asahiro, Yuichi
× Doi, Yuya
× 宮野, 英次
WEKO
6037
× Samizo, Kazuaki
× Shimizu, Hirotaka
|
|||||||||||||||||||||
| 抄録 | ||||||||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||||||||
| 内容記述 | In this paper we study the (in)approximability of two distance-based relaxed variants of the maximum clique problem (Max Clique), named Max d-Clique and Max d-Club: A d-clique in a graph G = (V,E) is a subset S ⊆ V of vertices such that for every pair of vertices u, v ∈ S, the distance between u and v is at most d in G. A d-club in a graph G = (V,E) is a subset S_ ⊆ V of vertices that induces a subgraph of G of diameter at most d. Given a graph G with n vertices, the goal of Max d-Clique (Max d-Club, resp.) is to find a d-clique (d-club, resp.) of maximum cardinality in G. Since Max 1- Clique and Max 1-Club are identical to Max Clique, the inapproximabilty for Max Clique shown by Zuckerman in 2007 is transferred to them. Namely, Max 1-Clique and Max 1-Club cannot be efficiently approximated within a factor of n1−ε for any ε > 0 unless P = NP. Also, in 2002, Marincek and Mohar showed that it is NP-hard to approximate Max d-Club to within a factor of n1/3−ε for any ε > 0 and any fixed d ≥ 2. In this paper, we strengthen the hardness result; we prove that, for any ε > 0 and any fixed d ≥ 2, it is NP-hard to approximate Max d-Club to within a factor of n1/2−ε. Then, we design a polynomial-time algorithm which achieves an optimal approximation ratio of O(n1/2) for any integer d ≥ 2. By using the similar ideas, we show the O(n1/2)-approximation algorithm for Max d-Clique for any d ≥ 2. This is the best possible in polynomial time unless P = NP, as we can prove the Ω(n1/2−ε)-inapproximability. | |||||||||||||||||||||
| 書誌情報 |
en : Algorithmica 巻 80, 号 6, p. 1834-1856, 発行日 2017-07-21 |
|||||||||||||||||||||
| 出版社 | ||||||||||||||||||||||
| 出版者 | Springer | |||||||||||||||||||||
| DOI | ||||||||||||||||||||||
| 識別子タイプ | DOI | |||||||||||||||||||||
| 関連識別子 | https://doi.org/10.1007/s00453-017-0344-y | |||||||||||||||||||||
| NCID | ||||||||||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||||||||||
| 収録物識別子 | AA10679010 | |||||||||||||||||||||
| ISSN | ||||||||||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||||||||||
| 収録物識別子 | 0178-4617 | |||||||||||||||||||||
| ISSN | ||||||||||||||||||||||
| 収録物識別子タイプ | EISSN | |||||||||||||||||||||
| 収録物識別子 | 1432-0541 | |||||||||||||||||||||
| 著作権関連情報 | ||||||||||||||||||||||
| 権利情報 | Copyright (c) Springer Science+Business Media, LLC 2017 | |||||||||||||||||||||
| キーワード | ||||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||||
| 主題 | d-clique | |||||||||||||||||||||
| キーワード | ||||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||||
| 主題 | d-club | |||||||||||||||||||||
| キーワード | ||||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||||
| 主題 | Maximum distance-bounded subgraph problems | |||||||||||||||||||||
| キーワード | ||||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||||
| 主題 | (In)approximability | |||||||||||||||||||||
| 出版タイプ | ||||||||||||||||||||||
| 出版タイプ | AM | |||||||||||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||||||||||
| 査読の有無 | ||||||||||||||||||||||
| 値 | yes | |||||||||||||||||||||
| 研究者情報 | ||||||||||||||||||||||
| https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html | ||||||||||||||||||||||
