Structure preserving reductions among convex optimization problems

摘要

In this paper we introduce the concept of convex optimization problem. Convex optimization problems are studied by giving a formalization of the concept of combinatorial structure, in terms of spectra of approximate solutions, and of reduction which preserves such structure. On this basis a classification of convex NP-optimization problems is introduced and is applied to study the combinatorial structure of several optimization problems associated to well-known NP-complete sets. Conditions on the approximability of such optimization problems are also given and it is shown that structurally isomorphic problems have similar approximability properties.