Hardprob/Maximum Set Splitting — различия между версиями

Текущая версия на 12:23, 22 сентября 2023

Коллекция C подмножеств конечного множества S.
Найти разбиение S, на непересекающиеся множества S₁ и S₂.
Максимизировать число подмножеств C, которые «разделены» между S₁ и S₂, т.е. не лежат полностью в S₁ или S₂.

@@ Строка 3: / Строка 3: @@
 * Найти разбиение <em>S</em>, на непересекающиеся множества <em>S<sub>1</sub></em> и <em>S<sub>2</sub></em>.
 * Максимизировать число подмножеств <em>C</em>, которые «разделены» между <em>S<sub>1</sub></em> и <em>S<sub>2</sub></em>, т.е. не лежат полностью в <em>S<sub>1</sub></em> или <em>S<sub>2</sub></em>.
 ----
 {{hard-problem-on-lab17|{{PAGENAME}}}}
 * {{has-testdata-and-visualization}}
-* {{has-pyomo-model}}
+* {{has-pyomo-model}}  {{vim|819542576}}
-* {{has-npc-reduction}}
+* {{has-npc-reduction}} {{vim|820790843}}
 * {{add-random-fuzzing-tests}}
 ----
@@ Строка 15: / Строка 14: @@
 {{ViggoCode|node145}}
 {{GDCode|SP4}}
-<!-- * [ Задача в википедии]  -->
+* [https://en.wikipedia.org/wiki/Set_splitting_problem Задача в википедии]
 </small>
 <!-- end -->
 [[Категория:ClassicHardProblems]]