Nastavit problém rozdělení - Set splitting problem

v teorie výpočetní složitosti, Nastavit rozdělení problém je následující rozhodovací problém: vzhledem k rodině F podmnožin konečné množiny S, rozhodnout, zda existuje oddíl S do dvou podmnožin S1, S2 tak, že všechny prvky F jsou rozděleny tímto oddílem, tj. žádný z prvků F je úplně v S1 nebo S2. Set Splitting je jedním z Garey & Johnson klasický NP-kompletní problémy.[1]

Varianty

Volá se optimalizační verze tohoto problému Max. Rozdělení a vyžaduje nalezení oddílu, který maximalizuje počet rozdělených prvků F. Je to APX-kompletní[2] problém a tudíž v NPO.

The Soubor k-Splitting problém je uveden následovně: daný S, Fa celé číslo k, existuje oddíl S který se rozdělí minimálně k podmnožiny F? Původní formulace je omezeným případem k rovnající se mohutnosti F. Sada k- Rozdělení je fixovatelný parametr, tj. pokud k považována za fixní parametr, spíše než za část vstupu, pak existuje polynomiální algoritmus pro jakoukoli fixní k. Dehne, Fellows a Rosamond představili algoritmus, který to včas vyřeší pro nějakou funkci F a konstantní C.[3]

Když každý prvek F je omezeno na přesnost mohutnosti kse nazývá varianta rozhodnutí Ek-Set rozdělení a optimalizační verze Maxk-Set rozdělení. Pro k > 2 bývalý zůstává NP kompletní a pro k ≥ 2 druhý zůstává APX kompletní.[4] Pro k ≥ 4, Ek-Set Splitting je aproximační odolný. To znamená, že pokud P = NP, neexistuje žádný polynomiální čas (faktor) aproximační algoritmus což je v podstatě lepší než náhodný oddíl.[5][6]

The Vážené rozdělení sady je varianta, ve které podmnožiny v F mít váhy a cílem je maximalizovat celkovou váhu rozdělených podmnožin.

Připojení k dalším problémům

Set Splitting je speciální případ Problém ne zcela stejné spokojenosti bez negovaných proměnných. Navíc, Ek-Set Splitting equals non-monochromatic zbarvení grafu z k-jednotný hypergrafy. Pro k= 2, optimalizační varianta se redukuje na dobře známou Maximální řez.[6]

Reference

  1. ^ Garey, Michael R.; Johnson, David S. (1979). Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti. New York: W.H. Freemane. ISBN  0-7167-1045-5.
  2. ^ Petrank, Erez (1994). "Tvrdost aproximace: Poloha mezery". Výpočetní složitost. Springer.
  3. ^ Dehne, Frank; Fellows, Michael; Rosamond, Frances (2003). Algoritmus FPT pro rozdělení sady (PDF). Grafové teoretické koncepty v informatice (WG2003), Přednášky z informatiky. 2880. Springer. 180–191.
  4. ^ Lovász, László (1973). Pokrytí a barvení hypergrafů. 4. jihovýchodní konference o kombinatorice, teorii grafů a výpočtech.
  5. ^ Håstad, Johan (2001). Msgstr "Některé optimální výsledky nepřístupnosti". Deník ACM. Sdružení pro výpočetní techniku. 48: 798–859. doi:10.1145/502090.502098.
  6. ^ A b Guruwami, Venkatesan (2003). "Výsledky nepřístupnosti pro problémy s rozdělením a uspokojivostí souboru bez smíšených klauzulí". Algorithmica. Springer. 38: 451–469. doi:10.1007 / s00453-003-1072-z.