AN EFFICIENT, STRONGLY POLYNOMIAL, EPSILON-APPROXIMATION PARAMETRIC OPTIMIZATION SCHEME

Given a set X subset of or equal to Z(n), vectors c, d is an element o f R-n, an interval [a, b] subset of R, a fixed 0 < epsilon < 1, and an oracle that, for any 0 < epsilon < 1 finds an epsilon-approximate sol ution to problem max(h(T)x \x is an element of X) for any h is an elem ent of R-n, we present a theoretically and practically efficient epsil on-approximation algorithm, for the problem min{upsilon(lambda) \ lamb da is an element of [a, b]}, where upsilon(lambda) = max{(c -lambda d) (T)x \ x is an element of X}. When the elements of the set X are {0, /-1} vectors, the total number of iterations required by our algorithm is O(n(7)(log n)(4)). (C) 1997 Elsevier Science B.V.