University of Rochester. Dept. of Computer Science
Published: 1994
Total Pages: 31
Get eBook
Abstract: "Extending a well known property of polynomially bounded NP optimization problems, we observe that, by attaching weights to tuples over the domain of the input, all NP optimization problems admit a certain logical characterization. We show that any NP optimization problem can be stated as a problem in which the constraint conditions can be expressed by a II2 first-order formula and this is the best possible result. We further analyze the weighted analogue of all syntactically defined classes of optimization problems that are known to have good approximation properties: MAX NP, MAX SNP, MAX SNP([pi]), MIN F[pi]1 and MIN F[pi]2(1). All these classes continue to have the same approximation properties in the case of positive weights. Using reductions from multiprover interactive systems, we show that if NP [not subset of] DTIME[2[superscript log[superscript O(1)] n]], the approximation properties of the above classes devaluates considerably when negative weights are also allowed (with the exception of MIN F+II1, where only a weaker deterioration could be proven). It follows that the general weighted versions of MAX 2SAT, Set Cover, Priority Ordering and of some other closely related natural problems are not approximable in quasipolynomial time within a factor of 2[superscript log [superscript [mu]] n] for some [mu]> 0 (which depends on the problem), unless NP [subset of] DTIME[2[superscript log [superscript O(1)] n]]. Under the same hypothesis, we show that the maximization variant of Set Partition is also not superpolylog approximable. A stronger result is proven for the minimization variant of Set Partition: if P [not equal to] NP, then MIN Set Partition cannot be approximated in polynomial time within a factor of n[supersript O(1)]."