Усиления субмодулярности

13

Набор-функция f монотонно субмодулярная , если для всех A,B ,

f(A)+f(B)f(AB)+f(AB).

Более сильным свойством является

f(A)+f(B)+f(C)+f(ABC)f(AB)+f(BC)+f(AC)+f(ABC).
Принимая , это свойство подразумевает монотонную субмодулярность.C=AB

Это свойство известно?

Фон

Это свойство возникло при попытке охарактеризовать функции покрытия. Учитывая некоторые взвешенные вселенную (все веса неотрицательны) и семейный X подмножеств U , функция охвата F ( S ) определяются для S X в общей массе элементов , охватываемых множества в S . Функция f всегда монотонна и субмодулярна. Обратное неверно.UXUf(S)SXSf

Из рассматриваемого свойства следует, что является функцией покрытия в случае | X | = 3 . Подобные, более сложные свойства работы для увеличения X . Все эти свойства удовлетворяются функциями покрытия, так что это полная характеристика.f|X|=3X

Юваль Фильмус
источник

Ответы:

13

Существует полная характеристика функций покрытия в терминах таких уравнений. Для | X |> 3 больше уравнений, чем указано. Каждое из этих уравнений можно рассматривать как ограничение на дискретную производную .kth

Монотонная функция увеличения тогда и только тогда, когда дискретная производная первого порядка равна + ve. т.е. , когда B .f(B)f(A)0AB

Субмодулярность тогда и только тогда, когда дискретная производная второго порядка равна -ve. т.е. .(f(AB)f(B))(f(A)f(AB))0

Аналогично, если у вас есть условия на следующие производных, вы получаете функции покрытия. (Я думаю, что знаки должны быть + ve для производной четного порядка и -ve для производной нечетного порядка)n

Нечто подобное уже было известно по вероятности. Функция покрытия также может рассматриваться как мера вероятности (вплоть до постоянной масштабирования). Единственное упоминание, которое мне удалось найти, - это страница 439 из книги Феллера о вероятности.

Ашвинкумар Б.В.
источник
f(A{x})f(A)f(A{x})+f(A{y})f(A{x,y})+f(A)A,B
7

Дискретные производные высшего порядка функций множества исследуются в Субмодулярности, супермодульности и монотонности высшего порядка псевдобулевых функций . Согласно им, строгое условие дискретной производной третьего порядка

f(AB)+f(AC)+f(BC)+f((AB)(AC)(BC))f(A(BC))+f(B(AC))+f(C(AB))+f(ABC).
The "aggregate" condition is mentioned in the paper "A characterization of a cone of pseudo-boolean functions via supermodularity-type inequalities" by Cramma, Hammer and Holtzman (inequality (4)), which is part of the rare collection "Quantitative Methoden in den Wirtschaftswissenschaften". This condition should be the same as mine.

Edit: The actual condition that Cramma, Hammer and Holtzman give is

f(A)+f(B)+f(C)+f(ABC)f(ABC)+f(AB)+f(AC)+f(BC).
If you put C=, you get submodularity.
Yuval Filmus
источник