Cтраница 1
Субмодулярные функции и матроиды являются источником большого числа важных минимаксных теорем, которые часто обобщают фундаментальные минимаксные теоремы теории графов, такие, как теоремы Кенига, Менгера и другие. [1]
Супермодулярные и субмодулярные функции часто позволяют нам формулировать и доказывать теоремы с чрезвычайно большой степенью унификации. [2]
Отыскание минимума субмодулярной функции множества на непустых собственных ( или только непустых, или только собственных) подмножествах некоего множества легко сводится к случаю отсутствия ограничений. Это сведение предоставляется читателю в качестве упражнения. [3]
Возможно также минимизировать субмодулярную функцию множества, определенную на всех подмножествах множества S, в пределах только нечетных подмножеств из S. [4]
Полиномиально временной алгоритм для минимизации субмодулярной функции множества известен ( см. Гречель, Ловас и Схрейвер ( 1981)) и мы не станем вдаваться в его детали, а ограничимся замечанием, что в нем применяется метод эллипсоидов, абсолютно так же, как при решении указанной выше задачи о паросочетании. [5]
Заметим, что задача максимизации произвольной субмодулярной функции является JVP-трудной даже для некоторых весьма изящных субмодулярных функций. [6]
К сожалению, этот подход к минимизации субмодулярной функции непрактичен, поскольку в нем используется метод эллипсоидов. Другой недостаток состоит в том, что он не дает какого-либо комбинаторного проникновения в структуру субмодулярных функций множеств. Поиск алгоритма минимизации субмодулярной функции множества, основанного на комбинаторных идеях, является важной открытой проблемой. [7]
Легко убедиться в том, что Д - субмодулярная функция. [8]
Легко видеть, что г ( Х) - субмодулярная функция множеств. [9]
Пусть S - конечное множество и /: 2s - R есть субмодулярная функция множества ( см. разд. Задача отыскания минимума для / является весьма общей комбинаторной проблемой оптимизации, включающей в себя ряд комбинаторных проблем оптимизации, рассмотренных в этой книге. [10]
Заметим, что задача максимизации произвольной субмодулярной функции является JVP-трудной даже для некоторых весьма изящных субмодулярных функций. [11]
С помощью довольно сложных рассуждений можно показать, что этот результат эквивалентен другим теоремам о субмодулярных функциях множеств, содержащихся в работах Эдмонд-са ( 1970), Эдмондса, Джайлса ( 1977) и Мартела ( 1981), но результат Франка, возможно, наиболее прост в изложении. [12]
Заметим, что функции множеств в примерах 1.3.12, 1.3.14 и 1.3.15 имеют несколько дополнительных свойств: г ( 0) 0, г монотонно не убывает и г ( ж) 1 для каждого элемента х 6 S. Конечное множество S, оснащенное такой субмодулярной функцией, называется матроидом, а г называется ранговой функцией матроида. [13]
К сожалению, этот подход к минимизации субмодулярной функции непрактичен, поскольку в нем используется метод эллипсоидов. Другой недостаток состоит в том, что он не дает какого-либо комбинаторного проникновения в структуру субмодулярных функций множеств. Поиск алгоритма минимизации субмодулярной функции множества, основанного на комбинаторных идеях, является важной открытой проблемой. [14]
Так, например, избыток - это субмодулярная, дефицит - супермодулярная, а мощность - модулярная функции на множестве вершин двудольного графа. Читателю предлагаем показать на примере, что если граф не двудольный, то его дефицит и избыток, вообще говоря, не являются ни супермодулярными, ни субмодулярными функциями. [15]