Lower Bounds for the Average and Smoothed Number of Pareto Optima
Lower Bounds for the Average and Smoothed Number of Pareto Optima
复制标题
帕累托最优平均数和平滑数的下界
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Luis Rademacher
中科院分区：
文献类型：
--
作者：
Navin Goyal;Luis Rademacher
多目标0-1线性优化的平滑分析最近引起了人们的关注。对于多目标优化问题，帕累托最佳解决方案的数量（即，在所有坐标中没有其他解决方案至少在所有坐标中都一样好的解决方案，至少在一个坐标中更好）是研究的中心对象。在本文中，我们证明了预期的Pareto Optima数量的几个小界限。我们的基本结果是Omega_d（n^（d-1））的下限，用于在相当一般的条件下在线性目标的分布中进行D目标和N变量的优化问题。我们的证明将降低帕累托最佳数量的问题与导致与超平面布置相关的几何形状相关联。我们使用基本结果来得出（1），这是自然多主体优化问题的第一个下限。我们用随机选择的边缘权重以最大的跨越树问题说明了这一点。我们的技术足够灵活，可以在此环境中研究的其他标准目标功能（例如，多目标最短路径，TSP Tour，匹配）产生这样的下限。 （2）min {omega_d（n^（d-1.5）phi^{（d-log d）（1-theta（1/phi））}），2^{theta（n）} $平滑的下限对于0-1的背包问题，对于phi-smirandom分布的D利润，用于knapsack问题的版本。这改善了Brunsch和Roeglin最近的下限。
Smoothed analysis of multiobjective 0-1 linear optimization has drawn considerable attention recently. The number of Pareto-optimal solutions (i.e., solutions with the property that no other solution is at least as good in all the coordinates and better in at least one) for multiobjective optimization problems is the central object of study. In this paper, we prove several lower bounds for the expected number of Pareto optima. Our basic result is a lower bound of Omega_d(n^(d-1)) for optimization problems with d objectives and n variables under fairly general conditions on the distributions of the linear objectives. Our proof relates the problem of lower bounding the number of Pareto optima to results in geometry connected to arrangements of hyperplanes. We use our basic result to derive (1) To our knowledge, the first lower bound for natural multiobjective optimization problems. We illustrate this for the maximum spanning tree problem with randomly chosen edge weights. Our technique is sufficiently flexible to yield such lower bounds for other standard objective functions studied in this setting (such as, multiobjective shortest path, TSP tour, matching). (2) Smoothed lower bound of min {Omega_d(n^(d-1.5) phi^{(d-log d) (1-Theta(1/phi))}), 2^{Theta(n)}}$ for the 0-1 knapsack problem with d profits for phi-semirandom distributions for a version of the knapsack problem. This improves the recent lower bound of Brunsch and Roeglin.