Decision Making Based on Approximate and Smoothed Pareto Curves
Heiner Ackermann, Alantha Newman, Heiko Röglin, Berthold Vöcking
We consider bicriteria optimization problems and investigate the
relationship between two standard approaches to solving them:
(i) computing the Pareto curve and
(ii) the so-called decision maker's approach in which both criteria
are combined into a single (usually non-linear) objective function.
Previous work by Papadimitriou and Yannakakis showed how to efficiently
approximate the Pareto curve for problems like Shortest Path, Spanning
Tree, and Perfect Matching}. We wish to determine for which classes of
combined objective functions the approximate Pareto curve also yields
an approximate solution to the decision maker's problem. We show that
an FPTAS for the Pareto curve also gives an FPTAS for the decision
maker's problem if the combined objective function is growth bounded like
a quasi-polynomial function. If these functions, however, show exponential
growth then the decision maker's problem is NP-hard to approximate within
any factor. In order to bypass these limitations of approximate decision
making, we turn our attention to Pareto curves in the probabilistic
framework of smoothed analysis. We show that in a smoothed model, we
can efficiently generate the (complete and exact) Pareto curve with a
small failure probability if there exists an algorithm for generating
the Pareto curve whose worst case running time is pseudopolynomial. This
way, we can solve the decision maker's problem w.r.t. any non-decreasing
objective function for randomly perturbed instances of, e.g., Shortest
Path, Spanning Tree, and Perfect Matching.