The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization

optimization problems is to enumerate the set of Pareto optimal
solutions, typically using some kind of dynamic programming approach.
Their running time, however, depends on the number of enumerated
solutions, which can be exponential in the worst case.

In this talk paper, I will present an almost tight bound on the expected number of Pareto optimal solutions for general bicriteria integer optimization problems in the framework of smoothed analysis.