Equivalence of ε -Approximate Separation and Optimization in Fixed Dimensions¹

Given a closed, convex set X\subseteq \bbR ⁿ , containing the origin, we consider the problem (P) : max  {c^\T x\colon x ∈ X} . We show that, for a fixed dimension, n , and fixed \eps , 0 <\eps<1 , the existence of a combinatorial, strongly polynomial \eps -approximation separation algorithm for the set X is equivalent to the existence of a combinatorial, strongly polynomial \eps -approximation optimization algorithm for the problem (P) .

Authors and Affiliations

1. Faculty of Administration, University of New Brunswick, Fredericton, New Brunswick, Canada E3B 5A3. kabadi@unb.ca., CA

   S. N. Kabadi

2. Faculty of Business Administration, University of Windsor, Windsor, Ontario, Canada N9B 3P4. aneja@uwindsor.ca., CA

   Y. P. Aneja

Received June 5, 1996; revised September 25, 1997.

Reprints and permissions