APPROXIMATING ORACLE MACHINES FOR COMBINATORIAL OPTIMIZATION

For every k, an oracle Turing machine M(k) and rational polytopes P-k( S) for all n and S subset of or equal to {0, 1}(n) are constructed; by querying from the set S given as an oracle, M(k)(S) solves the separa tion problem over P-k(S) in strongly polynomial time, performing O(n(3 k)) arithmetic operations. Each of the polytopes P-k(S) approximates S in the sense Pk(S) boolean AND {0, 1}(n) = S and P-k(S) subset of or equal to {0, 1}(n), andnes are obtained that, querying from the oracle S, maximize in polynomial time linear functionals over approximations for S obtained from P-k(S) by applying the cones-of-matrices cutting operator of Lovasz and Schrijver a constant (possibly zero) number of times. Thus, this construction enables a systematic application of the cones-of-matrices scheme to any combinatorial optimization problem.