Complexity classes for online problems with and without predictions

DOI10.1007/978-981-96-8312-3_4MaRDI QIDQ6897302zbMATH OpenFDO

Authors Magnus Berg, Joan Boyar, Lene M. Favrholdt, Kim S. Larsen

Publication date 20 November 2025

Full work available at URL https://doi.org/10.1007/978-981-96-8312-3_4

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• Advice complexity of priority algorithms
• Algorithm design
• Comparing the hardness of online minimization and maximization problems with predictions
• Depth-first search and the vertex cover problem
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• Information complexity of online problems
• Measuring the problem-relevant information in input
• Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover
• On the Advice Complexity of Online Problems
• On the complexity of algorithms with predictions for dynamic graph problems
• On the hardness of approximating minimum vertex cover
• On-line vertex-covering
• Online computation with advice
• Online dominating set
• Optimization, approximation, and complexity classes
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Randomization can be as helpful as a glimpse of the future in online computation
• Reducibility among combinatorial problems
• The advice complexity of a class of hard online problems
• The string guessing problem as a method to prove lower bounds on the advice complexity

Cited in

(1)

• Comparing the hardness of online minimization and maximization problems with predictions

This page was built for publication: Complexity classes for online problems with and without predictions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6897302)