Algorithmic extremal problems in combinatorial optimization

An efficient approximation algorithm generator for the generalized maximum ψ-satisfiability problem is presented which produces an efficient approximation algorithm ψ-MAXMEAN¹ for each finite set ψ of relations. The algorithms ψ-MAXMEAN¹ 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.