Revision as of 21:46, 22 October 2008 edit C. lorenz (talk \| contribs) 353 edits →NP optimization problems ← Previous edit		Revision as of 10:58, 14 December 2008 edit undo C. lorenz (talk \| contribs) 353 edits m →NP optimization problems Next edit →
Line 54: * ''NPO(V)'': :The class of NPO problems with polynomial-time algorithms approximating the optimal solution by a ratio bounded by some function on n. In Hromkovic's book, excluded from this class are all NPO(IV)-problems save if P=NP. Contains the [[TSP]] and [[Max Clique]] problems. Another class of interest is NPOPB, NPO with polynomially bounded cost functions. Problems with this condition ~~has~~have many desirable properties. ==Notes==

Optimization problem: Difference between revisions