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

DOI10.4230/LIPICS.ICALP.2017.35zbMATH Open1441.68285arXiv1707.01702MaRDI QIDQ5111366FDOQ5111366

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

Publication date: 27 May 2020

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

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

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)

Cited In (2)

• Total completion time scheduling under scenarios
• The difference between optimality and universality

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)