On the complexity of knapsack under explorable uncertainty: hardness and algorithms
From MaRDI portal
Cites work
- Algorithm design
- Competitive query minimization for stable matching with one-sided uncertainty
- Computational Complexity
- Computing shortest paths with uncertainty
- Computing the Median with Uncertainty
- Covering minimum spanning trees of random subgraphs
- Efficient update strategies for geometric computing with uncertainty
- Hardness of approximating _2p minimization problems
- scientific article; zbMATH DE number 7740865 (Why is no real title available?)
- Ignorance is almost bliss: near-optimal stochastic matching with few queries
- Learning-augmented query policies for minimum spanning tree with uncertainty
- Loss-less condensers, unbalanced expanders, and extractors
- Minimum spanning tree verification under uncertainty
- On sparsification of stochastic packing problems
- Query-competitive algorithms for cheapest set problems under uncertainty
- Query-Competitive Sorting with Uncertainty.
- Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
- Reducibility among combinatorial problems
- Set selection under explorable stochastic uncertainty via covering techniques
- Shortest‐path metric approximation for random subgraphs
- Special cases of the minimum spanning tree problem under explorable edge and vertex uncertainty
- Stochastic matching with few queries: (1-ε) approximation
- Stochastic packing integer programs with few queries
- Stochastic vertex cover with few queries
- The Minimum Cost Query Problem on Matroids with Uncertainty Areas.
- The minimum equivalent DNF problem and shortest implicants
- The robust knapsack problem with queries
- Verification problem of maximal points under uncertainty
This page was built for publication: On the complexity of knapsack under explorable uncertainty: hardness and algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7322392)
