Comparing the Hardness of Online Minimization and Maximization Problems with Predictions

Magnus Berg

doi:10.1007/978-981-96-8312-3_3

Comparing the Hardness of Online Minimization and Maximization Problems with Predictions

Magnus Berg^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

We build on the work of Berg, Boyar, Favrholdt, and Larsen, who developed a complexity theory for online problems with and without predictions (IJTCS-FAW 2025) where they define a hierarchy of complexity classes that classifies online problems based on the competitiveness of best possible deterministic online algorithms for each problem. Their work focused on online minimization problems and we continue their work by considering online maximization problems. First, we compare the competitiveness of the base online minimization problem from Berg, Boyar, Favrholdt, and Larsen, Asymmetric String Guessing, to the competitiveness of Online Bounded Degree Independent Set. Formally, we show that there exists algorithms of any given competitiveness for Asymmetric String Guessing if and only if there exists algorithms of the same competitiveness for Online Bounded Degree Independent Set, while respecting that the competitiveness of algorithms is measured differently for minimization and maximization problems. Moreover, we give several hardness preserving reductions between different online maximization problems, which imply new membership, hardness, and completeness results for the complexity classes. Finally, we show new positive and negative algorithmic results for (among others) Online Bounded Degree Independent Set, Online Interval Scheduling, Online Set Packing, and Online Bounded Degree Clique.

Original language	English
Title of host publication	Frontiers of Algorithmics - 19th International Joint Conference, IJTCS-FAW 2025, Proceedings
Editors	Vincent Chau, Christoph Dürr, Minming Li, Pinyan Lu
Publisher	Springer Science+Business Media
Publication date	2025
Pages	33-48
ISBN (Print)	978-981-96-8311-6
ISBN (Electronic)	978-981-96-8312-3
DOIs	https://doi.org/10.1007/978-981-96-8312-3_3
Publication status	Published - 2025
Event	19th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom, IJTCS-FAW 2025 - Paris, France Duration: 30. Jun 2025 → 2. Jul 2025

Conference

Conference	19th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom, IJTCS-FAW 2025
Country/Territory	France
City	Paris
Period	30/06/2025 → 02/07/2025

Series	Lecture Notes in Computer Science
Volume	15828 LNCS
ISSN	0302-9743

Keywords

Complexity Theory
Independent Set
Minimization vs Maximization
Online Algorithms with Predictions

Documents & Links

10.1007/978-981-96-8312-3_3

SDU Link

Check access to the material in SDU Library's search engine

1 Ph.D. thesis

Online Algorithms with Predictions
Møhring, M. B., 4. Nov 2025, Syddansk Universitet. Det Naturvidenskabelige Fakultet. 235 p.
Research output: Thesis › Ph.D. thesis

Open Access
File
38 Downloads (Pure)

Cite this

Berg, Magnus. / Comparing the Hardness of Online Minimization and Maximization Problems with Predictions. Frontiers of Algorithmics - 19th International Joint Conference, IJTCS-FAW 2025, Proceedings. editor / Vincent Chau ; Christoph Dürr ; Minming Li ; Pinyan Lu. Springer Science+Business Media, 2025. pp. 33-48 (Lecture Notes in Computer Science, Vol. 15828 LNCS).

@inproceedings{5c39dc853f70444588be9d54240de07b,

title = "Comparing the Hardness of Online Minimization and Maximization Problems with Predictions",

abstract = "We build on the work of Berg, Boyar, Favrholdt, and Larsen, who developed a complexity theory for online problems with and without predictions (IJTCS-FAW 2025) where they define a hierarchy of complexity classes that classifies online problems based on the competitiveness of best possible deterministic online algorithms for each problem. Their work focused on online minimization problems and we continue their work by considering online maximization problems. First, we compare the competitiveness of the base online minimization problem from Berg, Boyar, Favrholdt, and Larsen, Asymmetric String Guessing, to the competitiveness of Online Bounded Degree Independent Set. Formally, we show that there exists algorithms of any given competitiveness for Asymmetric String Guessing if and only if there exists algorithms of the same competitiveness for Online Bounded Degree Independent Set, while respecting that the competitiveness of algorithms is measured differently for minimization and maximization problems. Moreover, we give several hardness preserving reductions between different online maximization problems, which imply new membership, hardness, and completeness results for the complexity classes. Finally, we show new positive and negative algorithmic results for (among others) Online Bounded Degree Independent Set, Online Interval Scheduling, Online Set Packing, and Online Bounded Degree Clique.",

keywords = "Complexity Theory, Independent Set, Minimization vs Maximization, Online Algorithms with Predictions",

author = "Magnus Berg",

year = "2025",

doi = "10.1007/978-981-96-8312-3\_3",

language = "English",

isbn = "978-981-96-8311-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer Science+Business Media",

pages = "33--48",

editor = "Vincent Chau and Christoph D{\"u}rr and Minming Li and Pinyan Lu",

booktitle = "Frontiers of Algorithmics - 19th International Joint Conference, IJTCS-FAW 2025, Proceedings",

address = "United States",

note = "19th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom, IJTCS-FAW 2025 ; Conference date: 30-06-2025 Through 02-07-2025",

}

Berg, M 2025, Comparing the Hardness of Online Minimization and Maximization Problems with Predictions. in V Chau, C Dürr, M Li & P Lu (eds), Frontiers of Algorithmics - 19th International Joint Conference, IJTCS-FAW 2025, Proceedings. Springer Science+Business Media, Lecture Notes in Computer Science, vol. 15828 LNCS, pp. 33-48, 19th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom, IJTCS-FAW 2025, Paris, France, 30/06/2025. https://doi.org/10.1007/978-981-96-8312-3_3

Comparing the Hardness of Online Minimization and Maximization Problems with Predictions. / Berg, Magnus.
Frontiers of Algorithmics - 19th International Joint Conference, IJTCS-FAW 2025, Proceedings. ed. / Vincent Chau; Christoph Dürr; Minming Li; Pinyan Lu. Springer Science+Business Media, 2025. p. 33-48 (Lecture Notes in Computer Science, Vol. 15828 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Comparing the Hardness of Online Minimization and Maximization Problems with Predictions

AU - Berg, Magnus

PY - 2025

Y1 - 2025

N2 - We build on the work of Berg, Boyar, Favrholdt, and Larsen, who developed a complexity theory for online problems with and without predictions (IJTCS-FAW 2025) where they define a hierarchy of complexity classes that classifies online problems based on the competitiveness of best possible deterministic online algorithms for each problem. Their work focused on online minimization problems and we continue their work by considering online maximization problems. First, we compare the competitiveness of the base online minimization problem from Berg, Boyar, Favrholdt, and Larsen, Asymmetric String Guessing, to the competitiveness of Online Bounded Degree Independent Set. Formally, we show that there exists algorithms of any given competitiveness for Asymmetric String Guessing if and only if there exists algorithms of the same competitiveness for Online Bounded Degree Independent Set, while respecting that the competitiveness of algorithms is measured differently for minimization and maximization problems. Moreover, we give several hardness preserving reductions between different online maximization problems, which imply new membership, hardness, and completeness results for the complexity classes. Finally, we show new positive and negative algorithmic results for (among others) Online Bounded Degree Independent Set, Online Interval Scheduling, Online Set Packing, and Online Bounded Degree Clique.

AB - We build on the work of Berg, Boyar, Favrholdt, and Larsen, who developed a complexity theory for online problems with and without predictions (IJTCS-FAW 2025) where they define a hierarchy of complexity classes that classifies online problems based on the competitiveness of best possible deterministic online algorithms for each problem. Their work focused on online minimization problems and we continue their work by considering online maximization problems. First, we compare the competitiveness of the base online minimization problem from Berg, Boyar, Favrholdt, and Larsen, Asymmetric String Guessing, to the competitiveness of Online Bounded Degree Independent Set. Formally, we show that there exists algorithms of any given competitiveness for Asymmetric String Guessing if and only if there exists algorithms of the same competitiveness for Online Bounded Degree Independent Set, while respecting that the competitiveness of algorithms is measured differently for minimization and maximization problems. Moreover, we give several hardness preserving reductions between different online maximization problems, which imply new membership, hardness, and completeness results for the complexity classes. Finally, we show new positive and negative algorithmic results for (among others) Online Bounded Degree Independent Set, Online Interval Scheduling, Online Set Packing, and Online Bounded Degree Clique.

KW - Complexity Theory

KW - Independent Set

KW - Minimization vs Maximization

KW - Online Algorithms with Predictions

U2 - 10.1007/978-981-96-8312-3_3

DO - 10.1007/978-981-96-8312-3_3

M3 - Article in proceedings

AN - SCOPUS:105010827775

SN - 978-981-96-8311-6

T3 - Lecture Notes in Computer Science

SP - 33

EP - 48

BT - Frontiers of Algorithmics - 19th International Joint Conference, IJTCS-FAW 2025, Proceedings

A2 - Chau, Vincent

A2 - Dürr, Christoph

A2 - Li, Minming

A2 - Lu, Pinyan

PB - Springer Science+Business Media

T2 - 19th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom, IJTCS-FAW 2025

Y2 - 30 June 2025 through 2 July 2025

ER -

Berg M. Comparing the Hardness of Online Minimization and Maximization Problems with Predictions. In Chau V, Dürr C, Li M, Lu P, editors, Frontiers of Algorithmics - 19th International Joint Conference, IJTCS-FAW 2025, Proceedings. Springer Science+Business Media. 2025. p. 33-48. (Lecture Notes in Computer Science, Vol. 15828 LNCS). doi: 10.1007/978-981-96-8312-3_3