文章基本信息

标题：Lower Bounds for the Average and Smoothed Number of Pareto-Optima
本地全文：下载
作者：Tobias Brunsch ; Navin Goyal ; Luis Rademacher 等
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2014
卷号：10
页码：237-256
出版社：University of Chicago
摘要：Smoothed analysis of multiobjective $0$--$1$ linear optimization has drawn considerable attention recently. The goal is to give bounds for 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. In this article 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 finding lower bounds on the number of Pareto optima to results in discrete geometry and geometric probability about arrangements of hyperplanes. We use our basic result to derive the following results: (1) To our knowledge, the first lower bound for natural multiobjective optimization problems. We illustrate this on the maximum spanning tree problem with randomly chosen edge weights. Our technique is sufficiently flexible to yield such lower bounds also for other standard objective functions studied in this setting (such as multiobjective shortest path, TSP, matching). (2) A smoothed lower bound of $\min \{ \Omega_d( n^{d-1.5} \phi^d), 2^{\Theta_d(n)} \}$ for $\phi$-smooth instances of the $0$--$1$ knapsack problem with $d$ profits
关键词：multiobjective optimization; probabilistic analysis; smoothed analysis