基于LP松弛的客观稳健离散优化的黑盒削减问题

作者：Khaled Elbassioni

摘要：我们考虑稳健的离散最小化问题，其中不确定性由目标中的凸集定义。 我们展示了如何使用非稳健性问题的线性规划松弛的完整性间隙验证器来推导出稳健版本的近似算法。

原文标题：Some Black-box Reductions for Objective-robust Discrete Optimization Problems Based on their LP-Relaxations

原文摘要：We consider robust discrete minimization problems where uncertainty is defined by a convex set in the objective. We show how an integrality gap verifier for the linear programming relaxation of the non-robust version of the problem can be used to derive approximation algorithms for the robust version.

地址：https://arxiv.org/abs/1907.06786