パラメータ化近似アルゴリズム

パラメータ化近似アルゴリズムとは、入力サイズと特定のパラメータの関数に関して多項式時間でNP困難な最適化問題の近似解を求めることを目的としたアルゴリズムの一種です。これらのアルゴリズムは、従来の近似アルゴリズムと固定パラメータの扱いやすさという両方の長所を組み合わせるように設計されています。

従来の近似アルゴリズムでは、最適解から最大で特定の係数 $αだけ離れた解（$ $α$ 近似と呼ばれる）を多項式時間で見つけることを目標としています。一方、パラメータ化アルゴリズムは、問題の厳密解を見つけるように設計されていますが、アルゴリズムの実行時間は入力サイズと特定のパラメータ $k$ の関数に関して多項式であるという制約があります。このパラメータは入力の何らかの特性を表し、典型的なアプリケーションでは小さい値です。最適解を見つけることができるアルゴリズムが存在する場合、その問題は固定パラメータ扱い可能（FPT）であると言われます。 $f(k)n^{O(1)}$ 時間、 $f(k)$ $これは入力サイズn$ に依存しない関数です。

パラメータ化された近似アルゴリズムは、FPT時間で近似解を見つけることで、これら2つのアプローチのバランスを取ることを目指します。アルゴリズムは、 $α$ 近似を計算します。 $f(k)n^{O(1)}$ 時間、 $f(k)$ $は入力サイズn$ に依存しない関数です。このアプローチは、従来の近似法と比較して解の品質に対する保証を強化しつつ、FPT アルゴリズムと同様に効率的な実行時間を維持することで、従来のアプローチの限界を克服することを目的としています。パラメータ化された近似アルゴリズムを研究する研究分野の概要は、Marx の調査^{[ 1 ]}および Feldmann らによるより最近の調査^{[ 2 ]で確認できます。}

得られる近似比

パラメータ化された近似アルゴリズムの真の可能性は、与えられた最適化問題が $α$ 近似アルゴリズムを許容することが示された場合に活用されます。 $f(k)n^{O(1)}$ 対照的に、この問題には多項式時間 $α$ 近似アルゴリズムはありません (何らかの複雑性仮定の下で、例えば、 ${\mathsf {P}}\neq {\mathsf {NP}}$ $)、また、与えられたパラメータk$ に対する FPT アルゴリズム(つまり、少なくともW[1] 困難) もありません。

例えば、APX-困難かつW[1]-困難な問題の中には、パラメータ化近似スキーム（PAS）が許容されるものがある。すなわち、任意の $\varepsilon >0$ 1 $(1+\varepsilon )$ 近似値は以下のように計算できます。 $f(k,\varepsilon )n^{g(\varepsilon )}$ 一部の関数 $f$ と $g$ の時間。これにより、多項式時間近似と固定パラメータの扱いやすさの観点からの下限を回避します。PAS は、多項式時間近似スキーム (PTAS)と精神的には似ていますが、さらに与えられたパラメータ $k$ を利用します。PAS の実行時間における多項式の次数は関数に依存するため $g(\varepsilon )$ 、その値 $\varepsilon$ PASがFPT時間で実行されるためには、は任意だが定数であると仮定される。この仮定が不十分な場合、 $\varepsilon$ は、効率的なパラメータ化近似スキーム (EPAS)を得るためにパラメータとしても扱われ、任意の $\varepsilon >0$ を計算する $(1+\varepsilon )$ -近似 $f(k,\varepsilon )n^{O(1)}$ ある関数 $fの時間。これは$ 効率的な多項式時間近似スキーム (EPTAS)と精神的に似ています。

kカット

kカット問題には多項式時間がない $(2-\varepsilon )$ 任意の近似アルゴリズム $\varepsilon >0$ 仮定すると ${\mathsf {P}}\neq {\mathsf {NP}}$ および小集合拡張仮説。^{[ 3 ]}また、必要なコンポーネントの数 $k$ によってパラメータ化された W[1] 困難でもある。^{[ 4 ]}しかし、EPAS が存在し、 $(1+\varepsilon )$ -近似 $(k/\varepsilon )^{O(k)}n^{O(1)}$ 時間。^{[ 5 ]}

巡回セールスマン

巡回セールスマン問題は、倍増次元をパラメータとした場合、 APX困難かつパラNP困難である（ユークリッド平面ではNP困難である）。しかし、倍増次元をパラメータとした場合、EPASが存在し、より一般的なハイウェイ次元パラメータの場合にも存在する。^[⁶^]

シュタイナーツリー

シュタイナー木問題は、終端記号の数によってパラメータ化された FPT 問題です。^{[ 7 ]}しかし、最適解に含まれる非終端記号の数 $kからなる「双対」パラメータについては、この問題は$ W[2] 困難です (支配集合問題からの一般的な還元による)。シュタイナー木はAPX 困難であることも知られています。^{[ 8 ]}しかし、EPAS は、 $(1+\varepsilon )$ -近似 $2^{O(k^{2}/\varepsilon ^{4})}n^{O(1)}$ 時間。^{[ 9 ]}より一般的なシュタイナーフォレスト問題は、ツリー幅3のグラフではNP困難です。しかし、ツリー幅 $t$ のグラフではEPASは計算できます。 $(1+\varepsilon )$ -近似 $2^{O({\frac {t^{2}}{\varepsilon }}\log {\frac {t}{\varepsilon }})}n^{O(1)}}$ 時間。^{[ 10 ]}

強連結シュタイナー部分グラフ

強連結シュタイナー部分グラフ問題は、終端の数 $kでパラメータ化された W[1]-困難であることが知られており、$ ^{[ 11 ]}また、 $O(\log ^{2-\varepsilon }n)$ 多項式時間での近似（標準的な計算複雑性仮定の下で）。^{[ 12 ]}ただし、2近似はで計算できます。 $3knO(1)$ 時間。^{[ 13 ]}さらに、これは可能であり、 $(2-\varepsilon )$ 近似値は以下のように計算できます。 $f(k)n^{O(1)}$ Gap- ETHの下での任意の関数 $f$ の時間。^[¹⁴^]

k-中央値とk-平均値

中心の数 $k$ でパラメータ化された、よく研究されているk-メディアンおよびk-平均のメトリッククラスタリング問題については、 $(1+2/e-\varepsilon )$ -k-メディアンの近似となし $(1+8/e-\varepsilon )$ k-Meansの近似値は以下のように計算できます。 $f(k)n^{O(1)}$ Gap- ETHの下では、任意の関数 $f$ に対して時間が与えられます。^[¹⁵^]パラメータ化された一致近似アルゴリズムは存在しますが、^[¹⁵^]一致する近似を多項式時間で計算できるかどうかはわかりません。

クラスタリングは低次元データの設定で検討されることが多く、そのため、実用上関連のあるパラメータ化は、基となるメトリックの次元によるものです。ユークリッド空間では、k-Median問題とk-Means問題は^、次元 $d$ でパラメータ化されたEPAS [ ¹⁶^]^[¹⁷^]と、 $kでパラメータ化されたEPAS$ ^[¹⁸^]^[¹⁹^]を許容します。前者は、倍増次元によるパラメータ化のためのEPASに一般化されました。^[²⁰^]緩やかに関連するハイウェイ次元パラメータについては、現在までに XP実行時間の近似スキームのみが知られています。^[²¹^]

kセンター

メトリックk中心問題では、2 近似は多項式時間で計算できます。しかし、中心の数 $k$ ^{[ 22 ]} 、倍増次元(実際にはマンハッタン距離の次元) ^{[ 23 ]} 、またはハイウェイ次元^{[ 22 ]}のいずれかでパラメータ化する場合、パラメータ化された $(2-\varepsilon )$ 標準的な複雑性仮定の下では、近似アルゴリズムが存在します。さらに、k-Center 問題は、中心の数 $k 、$ 倍増次元、ハイウェイ次元、およびパス幅で同時にパラメータ化する場合、平面グラフでも W[1] 困難です。^[²⁴^] $ただし、 k$ と倍増次元を組み合わせるとEPAS が存在し、 ^[²⁴^] $k$ とハイウェイ次元を組み合わせる場合も同様です。^[²⁵^]頂点容量を持つより一般的なバージョンでは、k と倍増次元によるパラメータ化に対して EPAS が存在しますが、k とハイウェイ次元をパラメータとして使用する場合は存在しません。^[²⁶^]パス幅に関しては、k-Center は、より一般的なtreewidthパラメータに対しても、cliquewidthに対してもEPAS を許容します。^[²⁷^]

最も密度の高い部分グラフ

k-クリーク問題の最適化バリアントは、最も密度の高いk-サブグラフ問題（2項制約充足問題）であり、タスクは $k$ 個の頂点を持つサブグラフの中でエッジ数が最大となるものを見つけることです。 $(k-1)$ -サイズのマッチングを選択するだけで近似します $k/2$ $与えられた入力グラフでは、 k$ 個の頂点上のエッジの最大数は常に最大で ${k \choose 2}=k(k-1)/2$ これも漸近的に最適です。なぜなら、Gap- ETHの下では $k^{1-o(1)}$ $-近似は、 k$ でパラメータ化された FPT 時間で計算できます。^{[ 28 ]}

支配的なセット

支配集合問題では、任意の値を計算することはW[1]困難である。 $g(k)$ -近似 $f(k)n^{O(1)}$ 任意の関数 $g$ および $f$ の時間。^{[ 29 ]}

近似カーネル化

カーネル化は、固定パラメータ追跡可能性において、 NP困難問題のインスタンスを前処理して「容易な部分」を取り除き、インスタンスのNP困難な核を明らかにするために用いられる手法である。カーネル化アルゴリズムは、インスタンス $I$ とパラメータ $k$ を受け取り、新しいインスタンスを返す。 $I'$ パラメータ付き $k'$ サイズが $I'$ そして $k'$ $は入力パラメータk$ の関数として制限され、アルゴリズムは多項式時間で実行されます。α近似カーネル化アルゴリズムは $、$ パラメータ化近似アルゴリズムで使用されるこの手法の変種です。これはカーネルを返します。 $I'$ $β$ 近似は $I'$ 入力インスタンス $Iの$ $α β$ 近似に多項式時間で変換できます。この概念は Lokshtanov らによって導入されました^[³⁰^]が、文献にはチューリングカーネル^[³¹^]や $α忠実度カーネル化$ ^[³²^]など、関連する他の概念があります。

通常の（非近似）カーネルに関しては、問題がα近似カーネル化アルゴリズムを許容するのは、パラメータ化されたα近似アルゴリズムが存在する場合に限る。この事実の証明は、通常のカーネルの場合と非常によく似ている。^{[ 30 ]}ただし、保証された近似カーネルは、入力パラメータに対して指数関数的（またはそれ以上）なサイズになる可能性がある。したがって、多項式サイズの近似カーネルを許容する問題を見つけることが興味深い。さらに、多項式サイズの近似カーネル化スキーム（PSAKS）は、多項式サイズのカーネルを計算する $α$ 近似カーネル化アルゴリズムであり、 $αは$ 次のように設定できる。 $1+\varepsilon$ いかなる場合でも $\varepsilon >0$ 。

例えば、連結頂点被覆問題は解のサイズによってパラメータ化された FPT ですが、(通常の) 多項式サイズのカーネルは許容されません ( ${\textsf {NP}}\subseteq {\textsf {coNP/poly}}$ ）ですが、PSAKS は存在します。^{[ 30 ]}同様に、シュタイナー木問題は終端の数によってパラメータ化された FPT であり、多項式サイズのカーネルを許容しません（ただし、 ${\textsf {NP}}\subseteq {\textsf {coNP/poly}}$ ）、しかしPSAKSが存在する。^{[ 30 ]}シュタイナー木を最適解の非終端記号の数でパラメータ化すると、問題はW[2]困難（したがってFPT=W[2]でない限り、正確なカーネルは全く存在しない）になるが、それでもPSAKSが存在する。^{[ 9 ]}

パラメータ化近似に関する講演

Daniel Lokshtanov: k-Minカットのためのパラメータ化近似スキーム
Tuukka Korhonen: ツリー幅の単一指数時間 2 近似アルゴリズム
Karthik CS: 近似の最近の困難性により、パラメータ化された複雑性が生じる
アリエル・クリク著「パラメータ化近似への応用を伴う2変数漸化式」
メイラヴ・ゼハヴィ。FPT近似
ヴィンセント・コーエン氏による追記：様々なクラスタリング問題のパラメータ化された複雑性について
ファハド・パノラン著「独立した長方形集合のパラメータ化近似」
アンドレアス・エミール・フェルドマン著「シュタイナーネットワークの近似カーネル化スキーム」

参考文献

↑ Marx, Daniel (2008). "Parameterized Complexity and Approximation Algorithms" . The Computer Journal . 51 (1): 60–78 . doi : 10.1093/comjnl/bxm048 .
↑ Feldmann, Andreas Emil; Karthik C. S; Lee, Euiwoong; Manurangsi, Pasin (2020). "パラメータ化された複雑性における近似に関する調査: 困難性とアルゴリズム" . Algorithms . 13 (6): 146. arXiv : 2006.04411 . doi : 10.3390/a13060146 . ISSN 1999-4893 . この記事には、 CC BY 4.0ライセンスの下で利用可能なこの出典からのテキストが含まれています。
↑ Manurangsi, Pasin (2018). "Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis" . Algorithms . 11 (1): 10. arXiv : 1705.03581 . doi : 10.3390/a11010010 . ISSN 1999-4893 .
↑ G. Downey, Rodney; Estivill-Castro, Vladimir; Fellows, Michael; Prieto, Elena ; Rosamund, Frances A. (2003 年 4 月 1 日). "Cutting Up Is Hard To Do: The Parameterised Complexity of k-Cut and Related Problems" . Electronic Notes in Theoretical Computer Science . CATS'03, Computing: the Australasian Theory Symposium. 78 : 209– 222. doi : 10.1016/S1571-0661(04)81014-4 . hdl : 10230/36518 . ISSN 1571-0661 .
↑ Lokshtanov, Daniel; Saurabh, Saket; Surianarayanan, Vaishali (2022年4月25日). "A Parameterized Approximation Scheme for Min $k$-Cut" . SIAM Journal on Computing : FOCS20–205. arXiv : 2005.00134 . doi : 10.1137/20M1383197 . ISSN 0097-5397 .
↑エミル・フェルドマン、アンドレアス；フィルツァー、アーノルド（2025年1月）「高速道路の次元：メトリックな視点」、2025年ACM-SIAM離散アルゴリズムシンポジウム（SODA）論文集、応用数理学会論文集、pp. 3267–3276、doi：10.1137/1.9781611978322.104 、2025年6月2日取得
↑ Dreyfus, SE; Wagner, RA (1971). "グラフにおけるシュタイナー問題" . Networks . 1 (3): 195– 207. doi : 10.1002/net.3230010302 .
↑ミロスラフ、クレビク。 Chlebíková、Janka（2008年10月31日）。「グラフ上のシュタイナー木問題: 非近似性の結果」。理論的なコンピューターサイエンス。グローバルコンピューティングのアルゴリズム的側面。406 (3): 207–214。土井: 10.1016/j.tcs.2008.06.046。ISSN 0304-3975。
1 2ドヴォルザーク、パーヴェル。フェルドマン、アンドレアス E.クノップ、ドゥシャン。マサジーク、トマーシュ。トゥファール、トマーシュ。ヴェセリー、パベル（2021年1月1日）。「少数のシュタイナー頂点を持つシュタイナーツリーのパラメータ化された近似スキーム」。離散数学に関する SIAM ジャーナル。35 (1): 546–574 . arXiv : 1710.00668。土井：10.1137/18M1209489。ISSN 0895-4801。S2CID 3581913。
↑フェルドマン、アンドレアス・エミール。ランピス、マイケル（2024）。「幅有界グラフにおけるシュタイナーの森のパラメータ化されたアルゴリズム」。ブリングマンでは、カール。グローエ、マーティン。パピス、ガブリエレ。スヴェンソン、オラ (編)。第 51 回オートマトン、言語、およびプログラミングに関する国際コロキウム、ICALP 2024、2024 年 7 月 8 ～ 12 日、エストニア、タリン。リップス。 Vol. 297. ダグシュトゥール城 – Leibniz-Zentrum für Informatik。 61 :1–61:20。arXiv : 2402.09835。土井：10.4230/LIPICS.ICALP.2024.61。
↑ Guo, Jiong; Niedermeier, Rolf; Suchý, Ondřej (2011年1月1日). "Parameterized Complexity of Arc-Weighted Directed Steiner Problems" . SIAM Journal on Discrete Mathematics . 25 (2): 583– 599. doi : 10.1137/100794560 . ISSN 0895-4801 .
↑ Halperin, Eran; Krauthgamer, Robert (2003年6月9日). 「多対数近似不可能性」 .第35回ACM理論計算機科学シンポジウム（STOC '03）議事録. ニューヨーク州ニューヨーク市、米国：Association for Computing Machinery. pp. 585–594 . doi : 10.1145/780542.780628 . ISBN 978-1-58113-674-6. S2CID 8554166 .
↑ Chitnis, Rajesh; Hajiaghayi, MohammadTaghi; Kortsarz, Guy (2013). "Fixed-Parameter and Approximation Algorithms: A New Look". In Gutin, Gregory; Szeider, Stefan (eds.). Parameterized and Exact Computation . Lecture Notes in Computer Science. Vol. 8246. Cham: Springer International Publishing. pp. 110–122 . arXiv : 1308.3520 . doi : 10.1007 /978-3-319-03898-8_11 . ISBN 978-3-319-03898-8. S2CID 6796132 .
↑ Chitnis, Rajesh; Feldmann, Andreas Emil; Manurangsi, Pasin (2021年4月19日). "双方向シュタイナーネットワーク問題に対するパラメータ化近似アルゴリズム" . ACM Transactions on Algorithms . 17 (2): 12:1–12:68. arXiv : 1707.06499 . doi : 10.1145/3447584 . ISSN 1549-6325 . S2CID 235372580 .
1 2 Cohen-Addad, Vincent; Gupta, Anupam; Kumar, Amit; Lee, Euiwoong; Li, Jason (2019). Baier, Christel; Chatzigiannakis, Ioannis; Flocchini, Paola; Leonardi, Stefano (eds.). "k-Median と k-Means のタイト FPT 近似" .第 46 回国際オートマタ、言語、プログラミングに関するコロキウム (ICALP 2019) . Leibniz International Proceedings in Informatics (LIPIcs). 132 . ドイツ、ダグシュトゥール: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 42:1–42:14. doi : 10.4230/LIPIcs.ICALP.2019.42 . ISBN 978-3-95977-109-2. S2CID 139103417 .
↑ Kolliopoulos, Stavros G.; Rao, Satish (1999). "A Nearly Linear-Time Approximation Scheme for the Euclidean k-median Problem". In Nešetřil, Jaroslav (ed.). Algorithms - ESA' 99. Lecture Notes in Computer Science. Vol. 1643. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 378–389 . doi : 10.1007/3-540-48481-7_33 . ISBN 978-3-540-66251-8。
↑ Cohen-Addad, Vincent (2018). "低次元k-Meansのための高速近似スキーム". 2018年ACM-SIAM離散アルゴリズムシンポジウム（SODA）論文集. 応用数理学会. pp. 430–440 . arXiv : 1708.07381 . doi : 10.1137/1.9781611975031.29 . ISBN 978-1-61197-503-1. S2CID 30474859 .
↑ Feldman, Dan; Monemizadeh, Morteza; Sohler, Christian (2007年6月6日). 「弱いコアセットに基づくk平均クラスタリングのためのPTAS」 .第23回計算幾何学シンポジウム（SCG '07）論文集. ニューヨーク州ニューヨーク市、米国：Association for Computing Machinery. pp. 11–18 . doi : 10.1145/1247069.1247072 . ISBN 978-1-59593-705-6. S2CID 5694112 .
↑ Feldman, Dan; Langberg, Michael (2011年6月6日) 「データの近似とクラスタリングのための統一フレームワーク」。第43回ACM理論計算機科学シンポジウム（STOC '11）議事録。ニューヨーク州ニューヨーク、米国：Association for Computing Machinery。pp. 569–578。doi : 10.1145 / 1993636.1993712。ISBN 978-1-4503-0691-1. S2CID 2677556 .
↑ Cohen-Addad, Vincent; Feldmann, Andreas Emil; Saulpic, David (2021 年 10 月 31 日). "倍増メトリックにおけるクラスタリングのためのほぼ線形時間近似スキーム" . Journal of the ACM . 68 (6): 44:1–44:34. arXiv : 1812.08664 . doi : 10.1145/3477541 . ISSN 0004-5411 . S2CID 240476191 .
↑ Feldmann, Andreas Emil; Saulpic, David (2021年12月1日). "低ハイウェイ次元グラフにおけるクラスタリングのための多項式時間近似スキーム" . Journal of Computer and System Sciences . 122 : 72– 93. doi : 10.1016/j.jcss.2021.06.002 . ISSN 0022-0000 .
1 2 Feldmann, Andreas Emil (2019 年 3 月 1 日). "低ハイウェイ次元グラフにおける k-中心問題の固定パラメータ近似" . Algorithmica . 81 (3): 1031– 1052. arXiv : 1605.02530 . doi : 10.1007/s00453-018-0455-0 . ISSN 1432-0541 . S2CID 46886829 .
↑ Feder, Tomás; Greene, Daniel (1988年1月1日) 「近似クラスタリングのための最適アルゴリズム」。第20回ACM理論計算機科学シンポジウム（STOC '88）議事録。ニューヨーク州ニューヨーク：Association for Computing Machinery。pp. 434–444。doi : 10.1145 / 62212.62255。ISBN 978-0-89791-264-8. S2CID 658151 .
1 2 Feldmann, Andreas Emil; Marx, Dániel (2020年7月1日). "輸送ネットワークにおけるk-中心問題のパラメータ化された困難性" . Algorithmica . 82 (7): 1989– 2005. arXiv : 1802.08563 . doi : 10.1007/s00453-020-00683-w . ISSN 1432-0541 . S2CID 3532236 .
↑ Becker, Amariah; Klein, Philip N.; Saulpic, David (2018). Azar, Yossi; Bast, Hannah; Herman, Grzegorz (eds.). "Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension" . 26th Annual European Symposium on Algorithms (ESA 2018) . Leibniz International Proceedings in Informatics (LIPIcs). 112 . Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 8:1–8:15. doi : 10.4230/LIPIcs.ESA.2018.8 . ISBN 978-3-95977-081-1。
↑ Feldmann, Andreas Emil; Vu, Tung Anh (2022). "Generalized $k$ -Center: Distinguishing Doubling and Highway Dimension". In Bekos, Michael A.; Kaufmann, Michael (eds.). Graph-Theoretic Concepts in Computer Science . Lecture Notes in Computer Science. Vol. 13453. Cham: Springer International Publishing. pp. 215–229 . arXiv : 2209.00675 . doi : 10.1007/978-3-031-15914-5_16 . ISBN 978-3-031-15914-5。
↑ Katsikarelis, Ioannis; Lampis, Michael; Paschos, Vangelis Th. (2019年7月15日). "構造パラメータ、厳密な境界、および (k,r)-中心の近似" . Discrete Applied Mathematics . Combinatorial Optimization: between Practice and Theory. 264 : 90– 117. arXiv : 1704.08868 . doi : 10.1016/j.dam.2018.11.002 . ISSN 0166-218X .
↑ Dinur, Irit; Manurangsi, Pasin (2018). Karlin, Anna R. (編). "ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network" .第 9 回理論計算機科学イノベーション会議 (ITCS 2018) . Leibniz International Proceedings in Informatics (LIPIcs). 94 . ドイツ、ダグシュトゥール: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 36:1–36:20. doi : 10.4230/LIPIcs.ITCS.2018.36 . ISBN 978-3-95977-060-6. S2CID 4681120 .
↑ S., Karthik C.; Laekhanukit, Bundit; Manurangsi, Pasin (2018年6月20日). 「支配集合の近似におけるパラメータ化された複雑性について」 .第50回ACM SIGACT理論計算シンポジウム論文集. STOC 2018. ニューヨーク州ニューヨーク、米国: Association for Computing Machinery. pp. 1283–1296 . arXiv : 1711.11029 . doi : 10.1145 /3188745.3188896 . ISBN 978-1-4503-5559-9. S2CID 3170316 .
1 2 3 4 Lokshtanov, Daniel; Panolan, Fahad; Ramanujan, MS; Saurabh, Saket (2017年6月19日). "Lossy kernelization" .第49回ACM SIGACT理論計算機科学シンポジウム議事録（PDF） . STOC 2017. ニューヨーク州ニューヨーク、米国: Association for Computing Machinery. pp. 224–237 . doi : 10.1145/3055399.3055456 . ISBN 978-1-4503-4528-6. S2CID 14599219 .
↑ハーメリン、ダニー。クラッチ、ステファン。カロリーナ州ソウティス。ヴァールストロム、マグナス。呉、習（2015 年 3 月 1 日）。「多項式 (チューリング) カーネライゼーションの完全性理論」。アルゴリズミカ。71 (3): 702–730。土井: 10.1007/s00453-014-9910-8。ISSN 1432-0541。S2CID 253973283。
↑ Fellows, Michael R.; Kulik, Ariel; Rosamond, Frances; Shachnai, Hadas (2018 年 5 月 1 日). "忠実度を維持する変換によるパラメータ化近似" . Journal of Computer and System Sciences . 93 : 30– 40. doi : 10.1016/j.jcss.2017.11.001 . ISSN 0022-0000 .

[1] Marx, Daniel (2008). "Parameterized Complexity and Approximation Algorithms" . The Computer Journal . 51 (1): 60–78 . doi : 10.1093/comjnl/bxm048 .

[2] Feldmann, Andreas Emil; Karthik C. S; Lee, Euiwoong; Manurangsi, Pasin (2020). "パラメータ化された複雑性における近似に関する調査: 困難性とアルゴリズム" . Algorithms . 13 (6): 146. arXiv : 2006.04411 . doi : 10.3390/a13060146 . ISSN 1999-4893 . この記事には、 CC BY 4.0ライセンスの下で利用可能なこの出典からのテキストが含まれています。

[3] Manurangsi, Pasin (2018). "Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis" . Algorithms . 11 (1): 10. arXiv : 1705.03581 . doi : 10.3390/a11010010 . ISSN 1999-4893 .

[4] G. Downey, Rodney; Estivill-Castro, Vladimir; Fellows, Michael; Prieto, Elena ; Rosamund, Frances A. (2003 年 4 月 1 日). "Cutting Up Is Hard To Do: The Parameterised Complexity of k-Cut and Related Problems" . Electronic Notes in Theoretical Computer Science . CATS'03, Computing: the Australasian Theory Symposium. 78 : 209– 222. doi : 10.1016/S1571-0661(04)81014-4 . hdl : 10230/36518 . ISSN 1571-0661 .

[5] Lokshtanov, Daniel; Saurabh, Saket; Surianarayanan, Vaishali (2022年4月25日). "A Parameterized Approximation Scheme for Min $k$-Cut" . SIAM Journal on Computing : FOCS20–205. arXiv : 2005.00134 . doi : 10.1137/20M1383197 . ISSN 0097-5397 .

[6] エミル・フェルドマン、アンドレアス；フィルツァー、アーノルド（2025年1月）「高速道路の次元：メトリックな視点」、2025年ACM-SIAM離散アルゴリズムシンポジウム（SODA）論文集、応用数理学会論文集、pp. 3267–3276、doi：10.1137/1.9781611978322.104 、2025年6月2日取得

[7] Dreyfus, SE; Wagner, RA (1971). "グラフにおけるシュタイナー問題" . Networks . 1 (3): 195– 207. doi : 10.1002/net.3230010302 .

[8] ミロスラフ、クレビク。 Chlebíková、Janka（2008年10月31日）。「グラフ上のシュタイナー木問題: 非近似性の結果」。理論的なコンピューターサイエンス。グローバルコンピューティングのアルゴリズム的側面。406 (3): 207–214。土井: 10.1016/j.tcs.2008.06.046。ISSN 0304-3975。

[:5-9] 1 2ドヴォルザーク、パーヴェル。フェルドマン、アンドレアス E.クノップ、ドゥシャン。マサジーク、トマーシュ。トゥファール、トマーシュ。ヴェセリー、パベル（2021年1月1日）。「少数のシュタイナー頂点を持つシュタイナーツリーのパラメータ化された近似スキーム」。離散数学に関する SIAM ジャーナル。35 (1): 546–574 . arXiv : 1710.00668。土井：10.1137/18M1209489。ISSN 0895-4801。S2CID 3581913。

[10] フェルドマン、アンドレアス・エミール。ランピス、マイケル（2024）。「幅有界グラフにおけるシュタイナーの森のパラメータ化されたアルゴリズム」。ブリングマンでは、カール。グローエ、マーティン。パピス、ガブリエレ。スヴェンソン、オラ (編)。第 51 回オートマトン、言語、およびプログラミングに関する国際コロキウム、ICALP 2024、2024 年 7 月 8 ～ 12 日、エストニア、タリン。リップス。 Vol. 297. ダグシュトゥール城 – Leibniz-Zentrum für Informatik。 61 :1–61:20。arXiv : 2402.09835。土井：10.4230/LIPICS.ICALP.2024.61。

[11] Guo, Jiong; Niedermeier, Rolf; Suchý, Ondřej (2011年1月1日). "Parameterized Complexity of Arc-Weighted Directed Steiner Problems" . SIAM Journal on Discrete Mathematics . 25 (2): 583– 599. doi : 10.1137/100794560 . ISSN 0895-4801 .

[12] Halperin, Eran; Krauthgamer, Robert (2003年6月9日). 「多対数近似不可能性」 .第35回ACM理論計算機科学シンポジウム（STOC '03）議事録. ニューヨーク州ニューヨーク市、米国：Association for Computing Machinery. pp. 585–594 . doi : 10.1145/780542.780628 . ISBN 978-1-58113-674-6. S2CID 8554166 .

[13] Chitnis, Rajesh; Hajiaghayi, MohammadTaghi; Kortsarz, Guy (2013). "Fixed-Parameter and Approximation Algorithms: A New Look". In Gutin, Gregory; Szeider, Stefan (eds.). Parameterized and Exact Computation . Lecture Notes in Computer Science. Vol. 8246. Cham: Springer International Publishing. pp. 110–122 . arXiv : 1308.3520 . doi : 10.1007 /978-3-319-03898-8_11 . ISBN 978-3-319-03898-8. S2CID 6796132 .

[14] Chitnis, Rajesh; Feldmann, Andreas Emil; Manurangsi, Pasin (2021年4月19日). "双方向シュタイナーネットワーク問題に対するパラメータ化近似アルゴリズム" . ACM Transactions on Algorithms . 17 (2): 12:1–12:68. arXiv : 1707.06499 . doi : 10.1145/3447584 . ISSN 1549-6325 . S2CID 235372580 .

[:1-15] 1 2 Cohen-Addad, Vincent; Gupta, Anupam; Kumar, Amit; Lee, Euiwoong; Li, Jason (2019). Baier, Christel; Chatzigiannakis, Ioannis; Flocchini, Paola; Leonardi, Stefano (eds.). "k-Median と k-Means のタイト FPT 近似" .第 46 回国際オートマタ、言語、プログラミングに関するコロキウム (ICALP 2019) . Leibniz International Proceedings in Informatics (LIPIcs). 132 . ドイツ、ダグシュトゥール: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 42:1–42:14. doi : 10.4230/LIPIcs.ICALP.2019.42 . ISBN 978-3-95977-109-2. S2CID 139103417 .

[16] Kolliopoulos, Stavros G.; Rao, Satish (1999). "A Nearly Linear-Time Approximation Scheme for the Euclidean k-median Problem". In Nešetřil, Jaroslav (ed.). Algorithms - ESA' 99. Lecture Notes in Computer Science. Vol. 1643. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 378–389 . doi : 10.1007/3-540-48481-7_33 . ISBN 978-3-540-66251-8。

[17] Cohen-Addad, Vincent (2018). "低次元k-Meansのための高速近似スキーム". 2018年ACM-SIAM離散アルゴリズムシンポジウム（SODA）論文集. 応用数理学会. pp. 430–440 . arXiv : 1708.07381 . doi : 10.1137/1.9781611975031.29 . ISBN 978-1-61197-503-1. S2CID 30474859 .

[18] Feldman, Dan; Monemizadeh, Morteza; Sohler, Christian (2007年6月6日). 「弱いコアセットに基づくk平均クラスタリングのためのPTAS」 .第23回計算幾何学シンポジウム（SCG '07）論文集. ニューヨーク州ニューヨーク市、米国：Association for Computing Machinery. pp. 11–18 . doi : 10.1145/1247069.1247072 . ISBN 978-1-59593-705-6. S2CID 5694112 .

[19] Feldman, Dan; Langberg, Michael (2011年6月6日) 「データの近似とクラスタリングのための統一フレームワーク」。第43回ACM理論計算機科学シンポジウム（STOC '11）議事録。ニューヨーク州ニューヨーク、米国：Association for Computing Machinery。pp. 569–578。doi : 10.1145 / 1993636.1993712。ISBN 978-1-4503-0691-1. S2CID 2677556 .

[20] Cohen-Addad, Vincent; Feldmann, Andreas Emil; Saulpic, David (2021 年 10 月 31 日). "倍増メトリックにおけるクラスタリングのためのほぼ線形時間近似スキーム" . Journal of the ACM . 68 (6): 44:1–44:34. arXiv : 1812.08664 . doi : 10.1145/3477541 . ISSN 0004-5411 . S2CID 240476191 .

[21] Feldmann, Andreas Emil; Saulpic, David (2021年12月1日). "低ハイウェイ次元グラフにおけるクラスタリングのための多項式時間近似スキーム" . Journal of Computer and System Sciences . 122 : 72– 93. doi : 10.1016/j.jcss.2021.06.002 . ISSN 0022-0000 .

[:2-22] 1 2 Feldmann, Andreas Emil (2019 年 3 月 1 日). "低ハイウェイ次元グラフにおける k-中心問題の固定パラメータ近似" . Algorithmica . 81 (3): 1031– 1052. arXiv : 1605.02530 . doi : 10.1007/s00453-018-0455-0 . ISSN 1432-0541 . S2CID 46886829 .

[23] Feder, Tomás; Greene, Daniel (1988年1月1日) 「近似クラスタリングのための最適アルゴリズム」。第20回ACM理論計算機科学シンポジウム（STOC '88）議事録。ニューヨーク州ニューヨーク：Association for Computing Machinery。pp. 434–444。doi : 10.1145 / 62212.62255。ISBN 978-0-89791-264-8. S2CID 658151 .

[:3-24] 1 2 Feldmann, Andreas Emil; Marx, Dániel (2020年7月1日). "輸送ネットワークにおけるk-中心問題のパラメータ化された困難性" . Algorithmica . 82 (7): 1989– 2005. arXiv : 1802.08563 . doi : 10.1007/s00453-020-00683-w . ISSN 1432-0541 . S2CID 3532236 .

[25] Becker, Amariah; Klein, Philip N.; Saulpic, David (2018). Azar, Yossi; Bast, Hannah; Herman, Grzegorz (eds.). "Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension" . 26th Annual European Symposium on Algorithms (ESA 2018) . Leibniz International Proceedings in Informatics (LIPIcs). 112 . Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 8:1–8:15. doi : 10.4230/LIPIcs.ESA.2018.8 . ISBN 978-3-95977-081-1。

[26] Feldmann, Andreas Emil; Vu, Tung Anh (2022). "Generalized $k$ -Center: Distinguishing Doubling and Highway Dimension". In Bekos, Michael A.; Kaufmann, Michael (eds.). Graph-Theoretic Concepts in Computer Science . Lecture Notes in Computer Science. Vol. 13453. Cham: Springer International Publishing. pp. 215–229 . arXiv : 2209.00675 . doi : 10.1007/978-3-031-15914-5_16 . ISBN 978-3-031-15914-5。

[:4-27] Katsikarelis, Ioannis; Lampis, Michael; Paschos, Vangelis Th. (2019年7月15日). "構造パラメータ、厳密な境界、および (k,r)-中心の近似" . Discrete Applied Mathematics . Combinatorial Optimization: between Practice and Theory. 264 : 90– 117. arXiv : 1704.08868 . doi : 10.1016/j.dam.2018.11.002 . ISSN 0166-218X .

[28] Dinur, Irit; Manurangsi, Pasin (2018). Karlin, Anna R. (編). "ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network" .第 9 回理論計算機科学イノベーション会議 (ITCS 2018) . Leibniz International Proceedings in Informatics (LIPIcs). 94 . ドイツ、ダグシュトゥール: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 36:1–36:20. doi : 10.4230/LIPIcs.ITCS.2018.36 . ISBN 978-3-95977-060-6. S2CID 4681120 .

[29] S., Karthik C.; Laekhanukit, Bundit; Manurangsi, Pasin (2018年6月20日). 「支配集合の近似におけるパラメータ化された複雑性について」 .第50回ACM SIGACT理論計算シンポジウム論文集. STOC 2018. ニューヨーク州ニューヨーク、米国: Association for Computing Machinery. pp. 1283–1296 . arXiv : 1711.11029 . doi : 10.1145 /3188745.3188896 . ISBN 978-1-4503-5559-9. S2CID 3170316 .

[:0-30] 1 2 3 4 Lokshtanov, Daniel; Panolan, Fahad; Ramanujan, MS; Saurabh, Saket (2017年6月19日). "Lossy kernelization" .第49回ACM SIGACT理論計算機科学シンポジウム議事録（PDF） . STOC 2017. ニューヨーク州ニューヨーク、米国: Association for Computing Machinery. pp. 224–237 . doi : 10.1145/3055399.3055456 . ISBN 978-1-4503-4528-6. S2CID 14599219 .

[31] ハーメリン、ダニー。クラッチ、ステファン。カロリーナ州ソウティス。ヴァールストロム、マグナス。呉、習（2015 年 3 月 1 日）。「多項式 (チューリング) カーネライゼーションの完全性理論」。アルゴリズミカ。71 (3): 702–730。土井: 10.1007/s00453-014-9910-8。ISSN 1432-0541。S2CID 253973283。

[32] Fellows, Michael R.; Kulik, Ariel; Rosamond, Frances; Shachnai, Hadas (2018 年 5 月 1 日). "忠実度を維持する変換によるパラメータ化近似" . Journal of Computer and System Sciences . 93 : 30– 40. doi : 10.1016/j.jcss.2017.11.001 . ISSN 0022-0000 .

[ 1 ]

[ 2 ]で確認できます。

[ 3 ]

[ 4 ]

[ 5 ]

[

[ 7 ]

[ 8 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[

、

[

[

[

[

[

[ 23 ]

[

[

[ 28 ]

[ 29 ]

[

[