Алгоритмы оптимизации комбинаторных объектов в k-sum метрике [Глеб Евстропов]

Пусть у нас имеется некоторое множество A, элементам которого присвоены неотрицательные веса (например, рёбра неориентированного графа). Также неявно описывается множество интересующих нас подмножеств множества А (например, множество рёбер являющихся путями между s и t). Стандартной задачей является найти допустимое подмножество A минимального веса (кратчайший путь в нашем примере), также зачастую требуется найти минимаксный объект, то есть такой, что максимальный из использованных весов минимален. Задача оптимизации в метрике k-sum обобщает эти два варианта, требуя найти такое множество, что сумма k самых дорогих элементов минимальна. При этом, если элементов в допустимом множество меньше k, то дополним соответствующим количеством нулей. В докладе будет показано, что имея алгоритм решения задачи оптимизации с обычной суммой за время O(P(n)) мы можем решить задачу в k-sum метрике за время O(P(n) * n). В случае, если останется время, будет рассмотрен аналогичный подход для поиска приближённого решения и асимптотически более эффективные решения в некоторых частных случаях.