Title :
Weighted NP optimization problems: logical definability and approximation properties
Author_Institution :
Dept. of Comput. Sci., Rochester Univ., NY, USA
Abstract :
It is shown that all NP-optimization problems can be characterized by Π2 first-order formulae and that Π1 formulae are not sufficient for this goal. This generalizes the result of Kolaitis and Thakur (1990). The approximation properties of the weighted versions of MAX NP, MAX SNP, MAX SNP(π), MIN F+Π1 and MIN F+Π2(1) are analyzed and dramatic changes are observed when negative weights are allowed
Keywords :
approximation theory; computational complexity; optimisation; approximation properties; first-order formulae; logical definability; negative weights; weighted NP optimization problems; Character generation; Computer science; Constraint optimization; Cost function; Incentive schemes; Joining processes; Law; Legal factors; Optimization methods; Polynomials;
Conference_Titel :
Structure in Complexity Theory Conference, 1995., Proceedings of Tenth Annual IEEE
Conference_Location :
Minneapolis, MN
Print_ISBN :
0-8186-7052-5
DOI :
10.1109/SCT.1995.514724
