Разложение субмодулярной функции

Учитывая субмодульную функцию $f$ на $\Omega=X_1\cup X_2$ где $X_1$ а также $X_2$ не пересекаются и $f(S)=f_1(S\cap X_1)+f_2(S\cap X_2)$ , Вот $f_1$ а также $f_2$ субмодульный на $X_1$ а также $X_2$ соответственно.

Вот $X_1,X_2,f_1,f_2$ неизвестны и только значение запроса доступа к $f$ дано. Тогда есть ли алгоритм Polytime, который находит $X_1$ , Если есть несколько вариантов для $X_1$ любой из них должен быть в порядке.

Некоторые мысли Если мы сможем найти любые два элемента $t_1,t_2$ так что оба они принадлежат $X_1$ или принадлежат $X_2$ тогда мы можем объединить их и продолжить рекурсивно. Но не понятно, как реализовать такой шаг.

ds.algorithms submodularity Ашвинкумар Б.В.
источник

Вы хотите сказать, что

f (S) = f_{1} (S \cap X_{1}) + f_{2} (S \cap X_{2})

$f(S) = f_1(S \cap X_1) + f_2(S \cap X_2)$ где

f_{1}

$f_1$ а также

f_{2}

$f_2$ субмодульный на

X_{1}

$X_1$ а также

X_{2}

$X_2$ соответственно?

Чандра Чекури

Да, я действительно это имел в виду. Спасибо за указание на опечатку, я исправлю это.

Ашвинкумар Б.В.

Я не уверен, что то, что я говорю ниже, правильно, но вот идея. Взять произвольный элемент

e \in Ω

$e \in \Omega$ , Если

f (e) = f_{Ω - e} (e)

$f(e) = f_{\Omega-e}(e)$ тогда

e

$e$ не зависит от остальных элементов, поэтому мы можем выбрать

X_{1} = {e}

$X_1 = \{e\}$ а также

X_{2} = Ω - {e}

$X_2 = \Omega-\{e\}$ , В противном случае пусть

X

$X$ быть минимальным подмножеством включения

Ω - e

$\Omega-e$ такой, что

f (e) > f_{X} (e)

$f(e) > f_X(e)$ , Тогда казалось бы, что

X \cup {e}

$X \cup \{e\}$ должен быть в том же разделе, и, следовательно, мы можем сжать набор в один элемент и повторить, если он строго меньше, чем

Ω

$\Omega$ в противном случае мы заключаем, что желаемого раздела не существует.

Чандра Чекури

Решил сделать комментарий в ответ.

Чандра Чекури

Взять произвольный элемент $e \in \Omega$ , Если $f(e) = f_{\Omega-e}(e)$ тогда $e$ не зависит от остальных элементов, поэтому мы можем выбрать $X_1 = \{e\}$ а также $X_2 = \Omega-\{e\}$ , В противном случае пусть $X$ быть минимальным подмножеством включения $\Omega-e$ такой, что $f(e) > f_X(e)$ , затем $X \cup \{e\}$ должен быть в том же разделе. Если $X \cup \{e\} = \Omega$ мы заключаем, что нет желаемого раздела, в противном случае мы сокращаем этот набор в один элемент и рекурсивно.

Чандра Чекури
источник

Разложение субмодулярной функции

Ответы: