中間性

媒介性は、いくつかの項目が他の項目の間に置かなければならないという制約の下で、項目の集合を順序付けるという順序理論におけるアルゴリズム問題である。 ^[1]これはバイオインフォマティクスに応用されており^{[2] 、Opatrný (1979) によって}NP 完全であることが示された。^[3]

問題の説明

媒介性問題への入力は、順序付けられたアイテムの3つ組の集合である。これらの3つ組にリストされているアイテムは、与えられた各3つ組について、3つ組の中央のアイテムが他の2つのアイテムの間のどこかに出力に表示されるという特性を持つ、全順序に配置する必要がある。各3つ組のアイテムは、出力で連続している必要はない。^[1]^[3]

例

例えば、入力トリプルのコレクション

(2,1,3)、(3,4,5)、(1,4,5)、(2,4,1)、(5,2,3)

出力順序によって満たされる

3、1、4、2、5

しかし、

3、1、2、4、5。

これらの出力順序の最初のものでは、5 つの入力トリプルすべてにおいて、トリプルの中央の項目が他の 2 つの項目の間に表示されます。ただし、2 番目の出力順序では、項目 4 は項目 1 と 2 の間にはなく、トリプル (2,4,1) によって指定された要件と矛盾しています。

入力に、(1,2,3) と (2,3,1) のように、3 つの項目は同じだが中央の項目の選択が異なる 2 つのトリプルが含まれている場合、有効なソリューションはありません。ただし、このような矛盾するトリプルのペアを含まない、有効なソリューションのないトリプルのセットを形成するより複雑な方法があります。

複雑

Opatrný (1979) は、媒介問題 (有効な解が存在するかどうかをアルゴリズムが決定しなければならない問題) の決定バージョンが、 3-充足可能性からの還元とハイパーグラフ 2-彩色からの別の還元の2 つの方法でNP 完全であることを示した。^[3]しかし、順序付けられていないすべてのアイテムの 3 つ組が入力の順序付けられた 3 つ組で表されている場合、他のアイテムの間にない 2 つのアイテムのうち 1 つを順序付けの開始として選択し、このアイテムを含む 3 つ組を使用して残りのアイテムの各ペアの相対的な位置を比較することで、この問題は簡単に解決できます。

関連する問題として、満たされる三つ組の数を最大化する順序付けを見つける問題はMAXSNP 困難であり、これはP = NPでない限り、多項式時間で 1 に任意に近い近似比を達成することが不可能であることを意味する。^[1]順序付けされていないアイテムの三つ組ごとに順序付けされた三つ組を含む密なインスタンスであっても、解決または近似することは依然として困難である。^[4] トーナメントに限定された問題の最小バージョンは、多項式時間近似スキーム (PTAS) を持つことが証明された。^[5 ]アイテムをランダムに順序付けすることで、近似比 1/3 (期待値) を達成することができ、この単純な戦略は、ユニークゲーム予想が正しい場合、可能な限り最高の多項式時間近似を与える。^[6]また、半正定値計画法または組み合わせ法を使用して、任意の満足可能なインスタンスの三つ組の少なくとも半分を満たす順序付けを多項式時間で見つけることも可能である。 ^[1]^[7]

パラメータ化された複雑性では、制約集合Cから可能な限り多くの制約を満たす問題は、パラメータ化されたアルゴリズムによって発見された解の品質qとランダムな順序付けによって期待される品質| C |/3との差q − | C |/3でパラメータ化されると、固定パラメータで扱いやすくなります。^[8]

成功する保証はないが、貪欲なヒューリスティックは、実際に発生する媒介問題の多くの例に対して解決策を見つけることができます。^[2]

アプリケーション

媒介性の応用例の 1 つは、バイオインフォマティクスの遺伝子マッピングのプロセスの一部として現れます。特定の種類の遺伝子実験は、遺伝子マーカーの 3 つの配列の順序を決定するために使用できますが、遺伝子配列とその逆を区別しないため、このような実験から得られる情報では、3 つのマーカーのうちのどれが中央のマーカーであるかのみが決定されます。媒介性の問題は、この種の実験データを前提として、マーカーのコレクションを 1 つの配列に組み立てる問題を抽象化したものです。^[1]^[2]

媒介性問題は確率、因果関係、時間の理論をモデル化するためにも使われてきた。^[9]

参考文献

^ abcde Chor, Benny ; Sudan, Madhu (1998)、「中間性への幾何学的アプローチ」、SIAM Journal on Discrete Mathematics、11 (4): 511–523 (電子版)、doi :10.1137/S0895480195296221、MR 1640920。
^ abc スロニム、ドナ; クルグリャック、レオニード; スタイン、リンカーン;ランダー、エリック(1997)、「放射線ハイブリッドによるヒトゲノムマップの構築」、計算生物学ジャーナル、4 (4): 487–504、doi :10.1089/cmb.1997.4.487、PMID 9385541。
^ abc Opatrný, J. (1979)、「全順序付け問題」、SIAM Journal on Computing、8 (1): 111–114、doi :10.1137/0208008、MR 0522973。
^ Ailon, Nir; Alon, Noga (2007)、「完全密問題の難しさ」、Information and Computation、205 (8): 1117–1129、doi : 10.1016/j.ic.2007.02.006、MR 2340896。
^ Karpinski, Marek; Schudy, Warren (2011)、「トーナメントおよび関連するランキング問題における媒介問題に対する近似スキーム」、LA Goldberg、K. Jansen、R.Ravi、JDP Rolim (編)、Proc. APPROX 2011、RANDOM 2011、Lecture Notes in Computer Science、vol. 6845、pp. 277–288、arXiv : 0911.2214、doi :10.1007/978-3-642-22935-0_24、ISBN 978-3-642-22934-3、S2CID 7180847
^ チャリカー、モーゼス、グルスワミ、ベンカテサン、マノカラン、ラジセカール (2009)、「アリティ 3 のすべての順列 CSP は近似耐性がある」、第 24 回 IEEE 計算複雑性会議、pp. 62–73、doi :10.1109/CCC.2009.29、ISBN 978-0-7695-3717-7、MR 2932455、S2CID 257225。
^ Makarychev, Yury (2012)、「媒介性のための単純な線形時間近似アルゴリズム」、Operations Research Letters、40 (6): 450–452、doi :10.1016/j.orl.2012.08.008、MR 2998680。
^ グティン、グレゴリー、キム、ウン・ジョン、ムニッチ、マティアス、イェオ、アンダース (2010)、「タイトな下限値を超えてパラメータ化された中間性」、Journal of Computer and System Sciences、76 (8): 872–878、arXiv : 0907.5427、doi :10.1016/j.jcss.2010.05.001、MR 2722353、S2CID 3408698。
^ ヴァシェク、フヴァータル; Wu、Baoyindureng (2011)、「ライヘンバッハの因果関係について」、Erkenntnis、76 (1): 41–48、arXiv : 0902.1763、doi :10.1007/s10670-011-9321-z、S2CID 14123568。

[cs98-1] Chor, Benny ; Sudan, Madhu (1998)、「中間性への幾何学的アプローチ」、SIAM Journal on Discrete Mathematics、11 (4): 511–523 (電子版)、doi :10.1137/S0895480195296221、MR 1640920。

[sksl97-2] スロニム、ドナ; クルグリャック、レオニード; スタイン、リンカーン;ランダー、エリック(1997)、「放射線ハイブリッドによるヒトゲノムマップの構築」、計算生物学ジャーナル、4 (4): 487–504、doi :10.1089/cmb.1997.4.487、PMID 9385541。

[o79-3] Opatrný, J. (1979)、「全順序付け問題」、SIAM Journal on Computing、8 (1): 111–114、doi :10.1137/0208008、MR 0522973。

[4] Ailon, Nir; Alon, Noga (2007)、「完全密問題の難しさ」、Information and Computation、205 (8): 1117–1129、doi : 10.1016/j.ic.2007.02.006、MR 2340896。

[5] Karpinski, Marek; Schudy, Warren (2011)、「トーナメントおよび関連するランキング問題における媒介問題に対する近似スキーム」、LA Goldberg、K. Jansen、R.Ravi、JDP Rolim (編)、Proc. APPROX 2011、RANDOM 2011、Lecture Notes in Computer Science、vol. 6845、pp. 277–288、arXiv : 0911.2214、doi :10.1007/978-3-642-22935-0_24、ISBN 978-3-642-22934-3、S2CID 7180847

[6] チャリカー、モーゼス、グルスワミ、ベンカテサン、マノカラン、ラジセカール (2009)、「アリティ 3 のすべての順列 CSP は近似耐性がある」、第 24 回 IEEE 計算複雑性会議、pp. 62–73、doi :10.1109/CCC.2009.29、ISBN 978-0-7695-3717-7、MR 2932455、S2CID 257225。

[7] Makarychev, Yury (2012)、「媒介性のための単純な線形時間近似アルゴリズム」、Operations Research Letters、40 (6): 450–452、doi :10.1016/j.orl.2012.08.008、MR 2998680。

[8] グティン、グレゴリー、キム、ウン・ジョン、ムニッチ、マティアス、イェオ、アンダース (2010)、「タイトな下限値を超えてパラメータ化された中間性」、Journal of Computer and System Sciences、76 (8): 872–878、arXiv : 0907.5427、doi :10.1016/j.jcss.2010.05.001、MR 2722353、S2CID 3408698。

[9] ヴァシェク、フヴァータル; Wu、Baoyindureng (2011)、「ライヘンバッハの因果関係について」、Erkenntnis、76 (1): 41–48、arXiv : 0902.1763、doi :10.1007/s10670-011-9321-z、S2CID 14123568。