Mezi - Betweenness

Tento článek je o objednávání položek s omezeními. Pro ústřední postavení v sociálních sítích viz centralita mezi. Vztah mezi geometrií a geometrií viz uspořádaná geometrie.

Mezi je algoritmický problém v teorie objednávek o objednání kolekce předmětů podléhajících omezením, že některé položky musí být umístěny mezi ostatní.[1] Má aplikace v bioinformatika[2] a bylo prokázáno, že je NP-kompletní podle Opatrný (1979).[3]

Problémové prohlášení

Vstupem do problému rozdílu je sbírka objednané trojky položek. Položky uvedené v těchto trojicích by měly být umístěny do a celková objednávka, s vlastností, že pro každou z daných trojic se prostřední položka v trojici objeví na výstupu někde mezi dalšími dvěma položkami. Položky každé trojice nemusí být na výstupu za sebou.[1][3]

Příklady

Jako příklad se kolekce vstupů ztrojnásobí

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

je uspokojeno objednáním výstupu

3, 1, 4, 2, 5

ale ne tím

3, 1, 2, 4, 5.

V prvním z těchto výstupních uspořádání se u všech pěti vstupních trojic střední položka trojice objeví mezi dalšími dvěma položkami. U druhého výstupního řazení však položka 4 není mezi položkami 1 a 2, což je v rozporu s daným požadavkem trojnásobkem (2,4,1).

Pokud vstup obsahuje dvě trojice jako (1,2,3) a (2,3,1) se stejnými třemi položkami, ale s jinou volbou prostřední položky, pak neexistuje platné řešení. Existují však složitější způsoby, jak vytvořit soubor trojic bez platného řešení, které neobsahují takovou dvojici protichůdných trojic.

Složitost

Opatrný (1979) ukázal, že rozhodovací verze problému rozdílu (ve kterém musí algoritmus rozhodnout, zda existuje platné řešení, či nikoli) je NP-kompletní dvěma způsoby, a snížení z 3 - uspokojivost a také jinou redukcí od hypergraf 2-zbarvení.[3] Lze jej však snadno vyřešit, když jsou všechny neuspořádané trojice položek reprezentovány uspořádanou trojicí vstupu, výběrem jedné ze dvou položek, které nejsou mezi žádnými jinými, jako začátek objednávání a poté pomocí trojic, které se tohoto týkají položka k porovnání relativních pozic každé dvojice zbývajících položek.

Související problém s nalezením objednávky, která maximalizuje počet spokojených trojčat, je MAXSNP - tvrdé, což znamená, že je nemožné dosáhnout přibližný poměr libovolně blízko 1 palce polynomiální čas ledaže P = NP.[1] Je těžké vyřešit nebo přiblížit se i u hustých instancí, které zahrnují objednanou trojici pro každou možnou neuspořádanou trojici položek.[4] Ukázalo se, že minimální verze problému omezeného na turnaje má polynomiální schémata přibližování času (PTAS).[5]Dá se dosáhnout aproximačního poměru 1/3 (v očekávání) náhodným uspořádáním položek a tato jednoduchá strategie poskytuje nejlepší možnou aproximaci polynomiálního času, pokud domněnky o jedinečných hrách je pravda.[6] Je také možné použít semidefinitní programování nebo kombinatorické metody k nalezení uspořádání, které splňuje alespoň polovinu trojic jakékoli uspokojivé instance v polynomiálním čase.[1][7]

v parametrizovaná složitost, problém uspokojení co nejvíce omezení ze sady C omezení je fixovatelný parametr při parametrizaci rozdílem q − |C| / 3 mezi kvalitou řešení q nalezeno parametrizovaným algoritmem a |C| / 3 kvalita zaručená v očekávání náhodným objednáním.[8]

Ačkoli není zaručeno, že uspěje, a chamtivý heurista může najít řešení mnoha případů problému rozdílu vznikajících v praxi.[2]

Aplikace

Jedna aplikace mezičlánku vyvstává v bioinformatika jako součást procesu genové mapování. Určité typy genetických experimentů lze použít k určení pořadí trojic genetických markerů, ale nerozlišují genetickou sekvenci od jejího obrácení, takže informace získané z takového experimentu určují pouze to, který ze tří markerů je prostřední. Problém interness je abstrakcí problému sestavení kolekce markerů do jedné sekvence s ohledem na experimentální data tohoto typu.[1][2]

Problém prostornosti byl také použit k modelování teorií pravděpodobnost, kauzalita, a čas.[9]

Reference

  1. ^ A b C d E Chor, Benny; Súdán, Madhu (1998), „Geometrický přístup k mezičasu“, SIAM Journal on Discrete Mathematics, 11 (4): 511–523 (elektronická verze), doi:10.1137 / S0895480195296221, PAN  1640920.
  2. ^ A b C Slonim, Donna; Kruglyak, Leonid; Stein, Lincoln; Lander, Eric (1997), „Vytváření map lidského genomu pomocí radiačních hybridů“, Journal of Computational Biology, 4 (4): 487–504, doi:10.1089 / cmb.1997.4.487.
  3. ^ A b C Opatrný, J. (1979), "Total ordering problem", SIAM Journal on Computing, 8 (1): 111–114, doi:10.1137/0208008, PAN  0522973.
  4. ^ Ailon, Nir; Alon, Noga (2007), „Tvrdost plně hustých problémů“, Informace a výpočet, 205 (8): 1117–1129, doi:10.1016 / j.ic.2007.02.006, PAN  2340896.
  5. ^ Karpinski, Marek; Schudy, Warren (2011), „Aproximační schémata pro problém rozdílu v turnajích a související problémy s hodnocením“, L.A. Goldberg a K. Jansen a R. Ravi a J.D.P. Rolim (ed.), Proc. Přibližně 2011, NÁHODNÉ 2011, Přednášky z informatiky, 6845, str. 277–288, doi:10.1007/978-3-642-22935-0_24
  6. ^ Charikar, Mojžíš; Guruwami, Venkatesan; Manokaran, Rajsekar (2009), „Každý permutační CSP arity 3 je odolný vůči přiblížení“, 24. výroční konference IEEE o výpočetní složitosti, str. 62–73, doi:10.1109 / CCC.2009.29, PAN  2932455.
  7. ^ Makarychev, Yury (2012), „Algoritmus jednoduchého lineárního aproximace času mezi“, Dopisy o operačním výzkumu, 40 (6): 450–452, doi:10.1016 / j.orl.2012.08.008, PAN  2998680.
  8. ^ Gutin, Gregory; Kim, Eun Jung; Mnich, Matthias; Yeo, Anders (2010), „Mezi parametrizací nad těsně dolní mezí“, Journal of Computer and System Sciences, 76 (8): 872–878, arXiv:0907.5427, doi:10.1016 / j.jcss.2010.05.001, PAN  2722353.
  9. ^ Chvátal, Vašek; Wu, Baoyindureng (2011), „O Reichenbachově kauzálním rozprostření“, Erkenntnis, 76 (1): 41–48, arXiv:0902.1763, doi:10.1007 / s10670-011-9321-z.