English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Smoothed analysis of multiobjective 0-1 linear optimization has drawnconsiderable attention recently. The number of Pareto-optimal solutions (i.e.,solutions with the property that no other solution is at least as good in allthe coordinates and better in at least one) for multiobjective optimizationproblems is the central object of study. In this paper, we prove several lowerbounds for the expected number of Pareto optima. Our basic result is a lowerbound of \Omega_d(n^(d-1)) for optimization problems with d objectives and nvariables under fairly general conditions on the distributions of the linearobjectives. Our proof relates the problem of lower bounding the number ofPareto optima to results in geometry connected to arrangements of hyperplanes.We use our basic result to derive (1) To our knowledge, the first lower boundfor natural multiobjective optimization problems. We illustrate this for themaximum spanning tree problem with randomly chosen edge weights. Our techniqueis sufficiently flexible to yield such lower bounds for other standardobjective functions studied in this setting (such as, multiobjective shortestpath, 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 knapsackproblem with d profits for phi-semirandom distributions for a version of theknapsack problem. This improves the recent lower bound of Brunsch and Roeglin.

Lower Bounds for the Average and Smoothed Number of Pareto Optima