Михайлюк В. А.
О пороге отношения аппроксимации для реоптимизации задачи о максимальном количестве выполненных уравнений в линейных системах над конечным полем

When an arbitrary equation is inserted into a linear system over field GF(2) that contains exactly 3 variables from the set of n variables in each equation, the problem of the maximum number of satisfied equations is reoptimized with the approximation ratio 3/2. This approximation ratio is a threshold. A similar result is true for systems that contain k variables in each equation if <$E k ~=~ O ( log n )>.

При выполнении уникальной игровой гипотезы (UGC) для задачи Ins - Max - E3CSP - EQUAL (реоптимизация Max - E3CSP - EQUAL при добавлении одного ограничения) существует полиномиальный оптимальный (пороговый) <$E symbol f ( alpha sub EQU )>-приближенный алгоритм, где <$E alpha sub EQU~symbol Ы~0,796> пороговое отношение аппроксимации Max - E3CSP - EQUAL и <$E symbol f ( alpha sub EQU )> = 1/<$E (2~-~alpha sub EQU )~symbol Ы~0,831>.

PDF