Open Journal of Mathematical Optimization

Multi-Stage Selection under Bounded Variation
Christoph Buchheim1; Maja Hügging1
1Department of Mathematics, TU Dortmund University, Vogelpothsweg 87, 44227 Dortmund, Germany
Open Journal of Mathematical Optimization, Volume 7 (2026), article no. 4, 18 p.

We investigate a multi-stage version of the selection problem where the variation between solutions in consecutive stages is either penalized in the objective function or bounded by hard constraints. While the former problem turns out to be tractable, the complexity of the latter problem depends on the type of bounds imposed: When bounding the number of changes of a single item over all stages, the problem turns out to be strongly NP-hard in general, even if we may select only one item per stage and each item may change only twice over all stages. In contrast, when the number of changes at each stage is bounded over all items, the problem can be efficiently solved by reducing it to a minimum-cost flow problem.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/ojmo.52
Keywords: Multi-Stage Optimization, Selection Problem, Bounded Variation

Christoph Buchheim  1 ; Maja Hügging  1

1 Department of Mathematics, TU Dortmund University, Vogelpothsweg 87, 44227 Dortmund, Germany
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
Christoph Buchheim; Maja Hügging. Multi-Stage Selection under Bounded Variation. Open Journal of Mathematical Optimization, Volume 7 (2026), article  no. 4, 18 p.. doi: 10.5802/ojmo.52
@article{OJMO_2026__7__A4_0,
     author = {Christoph Buchheim and Maja H\"ugging},
     title = {Multi-Stage {Selection} under {Bounded} {Variation}},
     journal = {Open Journal of Mathematical Optimization},
     eid = {4},
     pages = {1--18},
     year = {2026},
     publisher = {Universit\'e de Montpellier},
     volume = {7},
     doi = {10.5802/ojmo.52},
     language = {en},
     url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.52/}
}
TY  - JOUR
AU  - Christoph Buchheim
AU  - Maja Hügging
TI  - Multi-Stage Selection under Bounded Variation
JO  - Open Journal of Mathematical Optimization
PY  - 2026
SP  - 1
EP  - 18
VL  - 7
PB  - Université de Montpellier
UR  - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.52/
DO  - 10.5802/ojmo.52
LA  - en
ID  - OJMO_2026__7__A4_0
ER  - 
%0 Journal Article
%A Christoph Buchheim
%A Maja Hügging
%T Multi-Stage Selection under Bounded Variation
%J Open Journal of Mathematical Optimization
%] 4
%D 2026
%P 1-18
%V 7
%I Université de Montpellier
%U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.52/
%R 10.5802/ojmo.52
%G en
%F OJMO_2026__7__A4_0

[1] Evripidis Bampis; Dimitris Christou; Bruno Escoffier; Alexander Kononov; Kim Thang Nguyen A simple rounding scheme for multistage optimization, Theor. Comput. Sci., Volume 907 (2022), pp. 1-10 | DOI | Zbl | MR

[2] Evripidis Bampis; Bruno Escoffier; Alexander Kononov LP-Based Algorithms for Multistage Minimization Problems, Approximation and Online Algorithms (WAOA 2020) (Lecture Notes in Computer Science), Volume 12806, Springer (2021), pp. 1-15 | DOI | Zbl | MR

[3] Evripidis Bampis; Bruno Escoffier; Michael Lampis; Vangelis Th. Paschos Multistage Matchings, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) (LIPIcs – Leibniz International Proceedings in Informatics), Volume 101, Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2018), p. 7:1-7:13 | Zbl | MR

[4] Evripidis Bampis; Bruno Escoffier; Kevin Schewior; Alexandre Teiller Online Multistage Subset Maximization Problems, Algorithmica, Volume 83 (2021) no. 8, pp. 2374-2399 | DOI | Zbl | MR

[5] Evripidis Bampis; Bruno Escoffier; Alexandre Teiller Multistage knapsack, J. Comput. Syst. Sci., Volume 126 (2022), pp. 106-118 https://www.sciencedirect.com/... | DOI | Zbl | MR

[6] Claude Berge; Alain Ghouila-Houri Programmes, jeux et réseaux de transport, Dunod, 1962, viii+254 pages | Zbl | MR

[7] Kateřina Böhmová; Yann Disser; Matúš Mihalák; Peter Widmayer Interval Selection with Machine-Dependent Intervals, Algorithms and Data Structures (Frank Dehne; Roberto Solis-Oba; Jörg-Rüdiger Sack, eds.) (Lecture Notes in Computer Science), Volume 8037, Springer (2013), pp. 170-181 | Zbl | DOI

[8] Robert Bredereck; Till Fluschnik; Andrzej Kaczmarczyk When Votes Change and Committees Should (Not), 31st International Joint Conference on Artificial Intelligence (IJCAI 2022) (2022), pp. 144-150 | DOI

[9] Christoph Buchheim; Maja Hügging The polytope of binary sequences with bounded variation, Discrete Optim., Volume 48 (2023), 100776, 22 pages | DOI | Zbl | MR

[10] Markus Chimani; Niklas Troost Multistage Shortest Path: Instances and Practical Evaluation, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023) (LIPIcs – Leibniz International Proceedings in Informatics), Volume 257, Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2023), p. 14:1-14:19 | DOI | MR

[11] Markus Chimani; Niklas Troost; Tilo Wiedera Approximating Multistage Matching Problems, Algorithmica, Volume 84 (2022) no. 8, pp. 2135-2153 | DOI | Zbl | MR

[12] Markus Chimani; Niklas Troost; Tilo Wiedera A general approximation for multistage subgraph problems, Procedia Comput. Sci., Volume 223 (2023), pp. 334-342 | DOI | Zbl | MR

[13] Till Fluschnik A Multistage View on 2-Satisfiability, Algorithms and Complexity (CIAC 2021) (Lecture Notes in Computer Science), Volume 12701, Springer (2021), pp. 231-244 | DOI | Zbl | MR

[14] Till Fluschnik; Pascal Kunz Bipartite Temporal Graphs and the Parameterized Complexity of Multistage 2-Coloring, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022) (LIPIcs – Leibniz International Proceedings in Informatics), Volume 221, Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2022), p. 16:1-16:18 | DOI | MR

[15] Till Fluschnik; Rolf Niedermeier; Valentin Rohm; Philipp Zschoche Multistage vertex cover, Theory Comput. Syst., Volume 66 (2022) no. 2, pp. 454-483 | Zbl | DOI | MR

[16] Till Fluschnik; Rolf Niedermeier; Carsten Schubert; Philipp Zschoche Multistage $s-t$ Path: Confronting Similarity with Dissimilarity, Algorithmica, Volume 85 (2023) no. 7, pp. 2028-2064 | DOI | Zbl | MR

[17] Marc Goerigk; Michael Hartisch An Introduction to Robust Combinatorial Optimization: Concepts, Models and Algorithms for Decision Making under Uncertainty, International Series in Operations Research & Management Science, 361, Springer, 2024 | DOI | MR

[18] Anupam Gupta; Kunal Talwar; Udi Wieder Changing Bases: Multistage Optimization for Matroids and Matchings, Automata, Languages, and Programming (ICALP 2014) (Javier Esparza; Pierre Fraigniaud; Thore Husfeldt; Elias Koutsoupias, eds.) (Lecture Notes in Computational Science and Engineering), Volume 8572, Springer (2014), pp. 563-575 | Zbl | MR

[19] Adam Kasperski; Paweł Zieliński Robust recoverable and two-stage selection problems, Discrete Appl. Math., Volume 233 (2017), pp. 52-64 | DOI | Zbl | MR

[20] Leon Kellerhals; Malte Renken; Philipp Zschoche Parameterized Algorithms for Diverse Multistage Problems, 29th Annual European Symposium on Algorithms (ESA 2021) (LIPIcs – Leibniz International Proceedings in Informatics), Volume 204, Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2021), p. 55:1-55:17 | DOI | Zbl | MR

[21] Stefan Lendl; Britta Peis; Veerle Timmermans Matroid bases with cardinality constraints on the intersection, Math. Program., Volume 194 (2022) no. 1-2, pp. 661-684 | DOI | Zbl | MR

[22] Daniel Lokshtanov; Amer E. Mouawad The complexity of independent set reconfiguration on bipartite graphs, ACM Trans. Algorithms, Volume 15 (2018) no. 1, 7, 19 pages | Zbl | DOI | MR

[23] Alexander Schrijver Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, 1986, xii+471 pages | Zbl | MR

[24] Alexander Schrijver Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, 24, Springer, 2003, xxxvii+1881 pages | Zbl

Cited by Sources: