Просмотр исходного текста страницы Citeseer/Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints (2013) 10.1.1.644.7488

{{checked|}}
{{citeseerlink|citeseer/Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints (2013) 10.1.1.644.7488|
Мы исследуем две новые задачи оптимизации — минимизацию подмодульной функции при условии ограничения на подмодульную нижнюю границу («подмодульное покрытие») и максимизация субмодулярной функции с учетом субмодулярного верхнего ограничения («субмодулярный ранец»).

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

Эти задачи часто ставятся как минимизация разности между субмодулярными функциями, что в худшем случае не поддается аппроксимации.

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

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

Мы приводим результаты твердости для обеих задач, показывая, что наши коэффициенты аппроксимации тесны вплоть до лог-факторов.

Наконец, мы эмпирически демонстрируем производительность и хорошие свойства масштабируемости наших алгоритмов.
}}
{{enddiv}}

[[Категория:CiteSeerArticles]]