Standard

A simple rounding scheme for multistage optimization. / Bampis, Evripidis; Christou, Dimitris; Escoffier, Bruno et al.

In: Theoretical Computer Science, Vol. 907, 12.03.2022, p. 1-10.

Research output: Contribution to journal › Article › peer-review

Harvard

Bampis, E, Christou, D, Escoffier, B, Kononov, A & Nguyen, KT 2022, 'A simple rounding scheme for multistage optimization', Theoretical Computer Science, vol. 907, pp. 1-10. https://doi.org/10.1016/j.tcs.2022.01.009

APA

Bampis, E., Christou, D., Escoffier, B., Kononov, A., & Nguyen, K. T. (2022). A simple rounding scheme for multistage optimization. Theoretical Computer Science, 907, 1-10. https://doi.org/10.1016/j.tcs.2022.01.009

Vancouver

Bampis E, Christou D, Escoffier B, Kononov A, Nguyen KT. A simple rounding scheme for multistage optimization. Theoretical Computer Science. 2022 Mar 12;907:1-10. Epub 2022 Jan 8. doi: 10.1016/j.tcs.2022.01.009

Author

Bampis, Evripidis ; Christou, Dimitris ; Escoffier, Bruno et al. / A simple rounding scheme for multistage optimization. In: Theoretical Computer Science. 2022 ; Vol. 907. pp. 1-10.

BibTeX

@article{ead5d3ca649b4eeb89fd1ce5cd77ce00,
title = "A simple rounding scheme for multistage optimization",
abstract = "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.",
keywords = "Approximation algorithms, LP-rounding, Multistage optimization",
author = "Evripidis Bampis and Dimitris Christou and Bruno Escoffier and Alexander Kononov and Nguyen, {Kim Thang}",
note = "Funding Information: This work was partially funded by the grant ANR-19-CE48-0016 from the French National Research Agency ( ANR ). The research of the fourth author is supported by the Russian Science Foundation , grant 21-41-09017 . Publisher Copyright: {\textcopyright} 2022 Elsevier B.V.",
year = "2022",
month = mar,
day = "12",
doi = "10.1016/j.tcs.2022.01.009",
language = "English",
volume = "907",
pages = "1--10",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier Science Publishing Company, Inc.",

}

RIS

TY - JOUR

T1 - A simple rounding scheme for multistage optimization

AU - Bampis, Evripidis

AU - Christou, Dimitris

AU - Escoffier, Bruno

AU - Kononov, Alexander

AU - Nguyen, Kim Thang

N1 - Funding Information: This work was partially funded by the grant ANR-19-CE48-0016 from the French National Research Agency ( ANR ). The research of the fourth author is supported by the Russian Science Foundation , grant 21-41-09017 . Publisher Copyright: © 2022 Elsevier B.V.

PY - 2022/3/12

Y1 - 2022/3/12

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - LP-rounding

KW - Multistage optimization

UR - http://www.scopus.com/inward/record.url?scp=85122933873&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2022.01.009

DO - 10.1016/j.tcs.2022.01.009

M3 - Article

AN - SCOPUS:85122933873

VL - 907

SP - 1

EP - 10

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -

ID: 35321989