Smoothed Analysis of Multiobjective Optimization
Smoothed Analysis of Multiobjective Optimization
复制标题
多目标优化的平滑分析
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
S. Teng
中科院分区：
文献类型：
--
作者：
Heiko Röglin;S. Teng
我们证明，使用有限数量的线性目标函数在任何多项式函数中，在平滑分析的模型中，有限数量的二进制优化问题是多项式的。帕累托最佳解决方案的矩，它使用我们的新技术产生了第一个非平凡浓度。多项式平滑复杂性的表征二进制优化问题，这是由于Beier和Vöcking的较早结果。
We prove that the number of Pareto-optimal solutions in any multiobjective binary optimization problem with a finite number of linear objective functions is polynomial in the model of smoothed analysis. This resolves a conjecture of Rene Beier. Moreover, we give polynomial bounds on all finite moments of the number of Pareto-optimal solutions, which yields the first non-trivial concentration bound for this quantity. Using our new technique, we give a complete characterization of polynomial smoothed complexity for binary optimization problems, which strengthens an earlier result due to Beier and Vöcking.