- Негладкая и гладкая по Гельдеру субмодулярная максимизация (arXiv)
Автор: Дуксан Ли, Нам Хо-Нгуен, Дабин Ли.
Аннотация: Исследуется задача максимизации непрерывной DR-субмодулярной функции, не обязательно гладкой. Мы доказываем, что непрерывный жадный алгоритм обеспечивает [(1−1/e)OPT−ε] гарантию, когда функция является монотонной и гладкой по Гельдеру, что означает, что он допускает непрерывный по Гельдеру градиент. Для функций, которые не являются дифференцируемыми или негладкими, мы предлагаем вариант алгоритма зеркального прокси, который достигает гарантии [(1/2)OPT−ε]. Мы применяем наши алгоритмические структуры для устойчивой субмодулярной максимизации и устойчивой к распределению субмодулярной максимизации в условиях неоднозначности Вассерштейна. В частности, метод зеркального прокси применяется к устойчивой субмодулярной максимизации для получения единственного допустимого решения, значение которого не меньше (1/2)OPT−ε. Для устойчивой к распределению максимизации в условиях неоднозначности Вассерштейна мы выводим и работаем над переформулировкой субмодулярно-выпуклого максимина, целевая функция которой является гладкой по Гельдеру, для которой мы можем применять как непрерывный жадный метод, так и метод зеркального прокси. △
2. Разрешение аппроксимируемости автономной и онлайновой немонотонной DR-субмодулярной максимизации над общими выпуклыми множествами (arXiv)
Автор: Лоай Муалем, Моран Фельдман.
Аннотация: В последние годы максимизация DR-субмодулярных непрерывных функций стала важной областью исследований со многими реальными приложениями в областях машинного обучения, систем связи, исследования операций и экономики. Большинство работ в этой области исследуют максимизацию с учетом ограничений выпуклого множества вниз из-за результата Vondrák (2013) о неаппроксимируемости. Однако Дурр и соавт. (2021) показали, что эту неприближимость можно обойти, доказав, что отношения аппроксимации являются функциями m, минимальной ℓ∞-нормы любого допустимого вектора. Учитывая это наблюдение, можно получить результаты для максимизации DR-субмодулярной функции с учетом общих ограничений на выпуклое множество, что привело к многочисленным работам по этой проблеме. Самым последним из них является автономный алгоритм аппроксимации с полиномиальным временем 14 (1−m), разработанный Du (2022). Однако для соответствующей онлайн-задачи известен только алгоритм субэкспоненциального времени 133√(1−m)-аппроксимации. В этой работе мы представляем онлайн-алгоритм с полиномиальным временем, соответствующий 14(1-m)-аппроксимации современного автономного алгоритма. Мы также представляем результат неаппроксимации, показывающий, что наш онлайн-алгоритм и автономный алгоритм Ду (2022) оптимальны в сильном смысле. Наконец, мы изучаем эмпирическую производительность нашего алгоритма и алгоритма Du (который ранее изучался только теоретически) и показываем, что они постоянно превосходят ранее предложенные алгоритмы в приложениях максимизации дохода, суммирования местоположения и квадратичного программирования.
