Title: Robust Min-Max (Regret) Optimization using Ordered Weighted Averaging Show Chinese title

Title: 基于有序加权平均的鲁棒最小最大（遗憾）优化

Abstract: In decision-making under uncertainty, several criteria have been studied to aggregate the performance of a solution over multiple possible scenarios. This paper introduces a novel variant of ordered weighted averaging (OWA) for optimization problems. It generalizes the classic OWA approach, which includes robust min-max optimization as a special case, as well as min-max regret optimization. We derive new complexity results for this setting, including insights into the inapproximability and approximability of this problem. In particular, we provide stronger positive approximation results that asymptotically improve the previously best-known bounds for the classic OWA approach. In computational experiments, we evaluate the quality of the proposed methods and compare the proposed setting with classic OWA and min-max regret approaches. Show Chinese abstract

Abstract: 在不确定性下的决策中，已经研究了几种准则来汇总解决方案在多个可能情景下的表现。 本文介绍了一种用于优化问题的有序加权平均（OWA）的新变体。 它推广了经典的OWA方法，该方法包括鲁棒最小最大优化作为特殊情况，以及最小最大遗憾优化。 我们推导了此设置的新复杂性结果，包括对此问题的不可近似性和可近似性的见解。 特别是，我们提供了更强的积极近似结果，这些结果在渐近意义上改进了经典OWA方法之前已知的最佳界限。 在计算实验中，我们评估了所提出方法的质量，并将所提出的设置与经典的OWA和最小最大遗憾方法进行了比较。