2010/12/06 by Tobias Brunsch, Brunsch, Tobias, Heiko Roeglin +1
Computer Science · Engineering · Mathematics · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Mathematical Approximation and Integration #Optimization and Packing Problems #cs.DS
paper · pdf · doi:10.48550/arxiv.1012.1163
arxiv created 2010/12/06 · openalex publication_date 2010/12/06 · arxiv updated 2015/03/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ϕ 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(n2d ϕ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 Ω((n ϕ)^(d-logd) ⋅ (1-Θ1/ϕ)) Pareto optimal solutions in expectation. For the bi-criteria case we present a higher lower bound of Ω(n2 ϕ^1 - Θ1/ϕ), which almost matches the known upper bound of O(n2 ϕ).