Model-driven optimization using adaptive probes

MaRDI QIDQ2934609zbMATH OpenFDO

Authors Sudipto Guha, Kamesh Munagala

Publication date 18 December 2014

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Adaptive uncertainty resolution in Bayesian combinatorial optimization problems
• How to probe for an extreme value
• Algorithms and adaptivity gaps for stochastic probing
• A robust optimization approach with probe-able uncertainty

Cited in

(15)

• Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem
• Two-stage robust optimization problems with two-stage uncertainty
• Model-based algorithm configuration with adaptive capping and prior distributions
• The benefit of adaptivity in the stochastic knapsack problem with dependence on the state of nature
• The update complexity of selection and related problems
• Submodular stochastic probing on matroids
• Adaptive uncertainty resolution in Bayesian combinatorial optimization problems
• The robust knapsack problem with queries
• Adaptivity in the stochastic blackjack knapsack problem
• Algorithms for queryable uncertainty
• The benefit of adaptivity in stochastic packing problems with probing
• Improvements and generalizations of stochastic knapsack and Markovian bandits approximation algorithms
• Query minimization under stochastic uncertainty
• A prophet inequality based approach to the adaptive ProbeTopK problem
• Minimizing average flow-time under knapsack constraint

This page was built for publication: Model-driven optimization using adaptive probes

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