Конкурентные алгоритмы на основе данных для онлайн-задач о рюкзаке и покрытия множества

При разработке онлайн-алгоритмов основное внимание, как правило, уделяется алгоритмам с гарантиями в наихудшем случае, например ограничениям на коэффициент конкурентности. Однако хорошо известно, что такие алгоритмы часто чрезмерно пессимистичны и демонстрируют неоптимальную производительность на входных данных, не являющихся наихудшими. В данной работе разработан подход к проектированию онлайн-алгоритмов на основе данных, которые сохраняют близкие к оптимальным гарантии в наихудшем случае и одновременно обучаются для эффективной работы на типичных входных данных. Наш подход заключается в выявлении классов политик, допускающих глобальные гарантии в наихудшем случае, с последующим обучением внутри этих классов на основе исторических данных. Мы демонстрируем этот подход на примере двух классических задач — онлайн-задачи о рюкзаке и онлайн-задачи покрытия множества, — доказывая конкурентные оценки для богатых классов политик в каждом случае. Кроме того, мы иллюстрируем практическую значимость подхода на примере тематического исследования, посвящённого зарядке электромобилей.