When the optimum is also blind: a new perspective on universal optimization

DOI10.4230/LIPICS.ICALP.2017.35MaRDI QIDQ5111366zbMATH OpenFDO

Authors Marek Adamczyk, Fabrizio Grandoni, Michał Włodarczyk, Stefano Leonardi

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1707.01702

zbMATH Keywords

stochastic optimizationapproximation algorithmssubmodularity

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Stochastic programming (90C15) Approximation algorithms (68W25)

Recommendations

• Set covering with our eyes closed
• Universal approximations for TSP, Steiner tree, and set cover
• Boosted sampling
• Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty
• Hedging uncertainty: approximation algorithms for stochastic optimization problems

Cited in

(6)

• Total completion time scheduling under scenarios
• Set selection under explorable stochastic uncertainty via covering techniques
• The difference between optimality and universality
• Total completion time scheduling under scenarios
• An o( n)-approximation for submodular facility location
• Online bipartite matching in the probe-commit model

This page was built for publication: When the optimum is also blind: a new perspective on universal optimization

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