Comparing the hardness of online minimization and maximization problems with predictions

DOI10.1007/978-981-96-8312-3_3MaRDI QIDQ6897303zbMATH OpenFDO

Authors Magnus Berg

Publication date 20 November 2025

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

zbMATH Keywords

complexity theoryindependent setminimization vs maximizationonline algorithms with predictions

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Cliques in graphs with bounded minimum degree
• Competitive Caching with Machine Learned Advice
• Complexity classes for online problems with and without predictions
• Fully online matching
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• scientific article; zbMATH DE number 1003261 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 7646025 (Why is no real title available?)
• Independent set with advice: the impact of graph knowledge (extended abstract)
• Learning-augmented maximum independent set
• Online algorithms for the maximum \(k\)-colorable subgraph problem
• Online clique clustering
• Online graph coloring with predictions
• Online independent sets.
• Online interval scheduling with predictions
• Online Minimum Spanning Tree with Advice
• Online set packing
• Reducibility among combinatorial problems
• The advice complexity of a class of hard online problems

Cited in

(1)

• Complexity classes for online problems with and without predictions

This page was built for publication: Comparing the hardness of online minimization and maximization problems with predictions

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