CONSTRUCTING THE MINIMIZATION DIAGRAM OF A 2-PARAMETER PROBLEM

Let P(lambda, mu) = min {f1(x) + lambda-f2(x) + mu-f3(x)\x is-an-element-of D}. We present a method that constructs P(lambda, mu) for all lambda, mu in a given interval in O(f.T(n) + f2) time, where f denotes the number of faces of P(lambda, mu) in the interval and T(n) denotes the time needed to solve the associated nonparametric problem.