Algorithmic extremal problems in combinatorial optimization |
| |
Authors: | Karl J Lieberherr |
| |
Affiliation: | Princeton University, Department of Electrical Engineering and Computer Science, Princeton, New Jersey 08544 USA |
| |
Abstract: | An efficient approximation algorithm generator for the generalized maximum ψ-satisfiability problem is presented which produces an efficient approximation algorithm ψ-MAXMEAN1 for each finite set ψ of relations. The algorithms ψ-MAXMEAN1 are shown to be best-possible in the class of polynomial algorithms (if P ≠ NP), in both absolute and relative terms. The algorithms are of wide applicability, because of the central position of the generalized maximum satisfiability problem among the class of combinatorial optimization problems. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|