A simple rounding scheme for multistage optimization

Evripidis Bampis, Dimitris Christou, Bruno Escoffier, Alexander Kononov, Kim Thang Nguyen

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

Аннотация

We consider the multistage framework introduced in (Gupta et al., Eisenstat et al., both in ICALP 2014), where we are given a time horizon and a sequence of instances of a (static) combinatorial optimization problem (one for each time step), and the goal is to find a sequence of solutions (one for each time step) reaching a tradeoff between the quality of the solutions in each time step and the stability/similarity of the solutions in consecutive time steps. We first introduce a novel rounding scheme, tailored for multistage problems, that accounts for the moving cost (or stability revenue) of adjacent solutions. Using this rounding scheme, we propose improved approximation algorithms for the multistage variants of Prize-Collecting Steiner Tree and Prize-Collecting Traveling Salesman problems. Furthermore, we introduce a 2-approximation algorithm for multistage Multi-Cut on trees, and we also show that our general scheme can be extended to maximization problems, by providing a 0.75-approximation algorithm for the multistage variant of MaxSat.

Язык оригиналаанглийский
Страницы (с-по)1-10
Число страниц10
ЖурналTheoretical Computer Science
Том907
Ранняя дата в режиме онлайн8 янв. 2022
DOI
СостояниеОпубликовано - 12 мар. 2022

Предметные области OECD FOS+WOS

  • 1.02.EX ИНФОРМАТИКА, ТЕОРИЯ И МЕТОДЫ

Fingerprint

Подробные сведения о темах исследования «A simple rounding scheme for multistage optimization». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать