Lower bounds for the smoothed number of Pareto optimal solutions

DOI10.1007/978-3-642-20877-5_41zbMATH Open1332.90232arXiv1012.1163OpenAlexW1817061570MaRDI QIDQ3010422FDOQ3010422

Authors: Tobias Brunsch, Heiko Röglin 

Publication date: 1 July 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: In 2009, Roeglin and Teng showed that the smoothed number of Pareto optimal solutions of linear multi-criteria optimization problems is polynomially bounded in the number $n$ of variables and the maximum density $phi$ of the semi-random input model for any fixed number of objective functions. Their bound is, however, not very practical because the exponents grow exponentially in the number $d+1$ of objective functions. In a recent breakthrough, Moitra and O'Donnell improved this bound significantly to $O(n^{2d}ph{i}^{d(d+1)/2})$. An "intriguing problem", which Moitra and O'Donnell formulate in their paper, is how much further this bound can be improved. The previous lower bounds do not exclude the possibility of a polynomial upper bound whose degree does not depend on $d$. In this paper we resolve this question by constructing a class of instances with $Omega((nphi{)}^{(d-logd)cdot(1-Theta1/phi)})$ Pareto optimal solutions in expectation. For the bi-criteria case we present a higher lower bound of $Omega(n^{2}ph{i}^{1-Theta1/phi})$, which almost matches the known upper bound of $O(n^{2}phi)$.

Full work available at URL: https://arxiv.org/abs/1012.1163

Recommendations

• scientific article; zbMATH DE number 6678440
• Lower bounds for the average and smoothed number of Pareto-optima

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29)

Cites Work

• Multicriteria Optimization
• Smoothed analysis of algorithms
• Random knapsack in expected polynomial time
• The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization
• Smoothed Analysis of Multiobjective Optimization

Cited In (6)

• The smoothed number of Pareto-optimal solutions in bicriteria integer optimization
• The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization
• The smoothed number of Pareto-optimal solutions in non-integer bicriteria optimization
• Lower bounds for the average and smoothed number of Pareto-optima
• Statistics of partial minima
• Title not available (Why is that?)

This page was built for publication: Lower bounds for the smoothed number of Pareto optimal solutions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3010422)