| Abstract: | In the present work we are interested in to provide a universal language for supporting formalisms to specify the approximation hierarchy system for an abstract NP‐hard optimization problem. This work grew from the idea of providing a categorical view of structural complexity to optimization problems. The direction is aimed towards actually exploring the connections among the structural complexity aspects and categorical concepts, which may be viewed in a high‐level, in a structuralistic sense. After introducing the optimization problems categories OPTS and OPT, as well as related questions, a formal system modelling the approximation hierarchy of a given optimization problem is provided, based on categorical shape theory. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim) |
