Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності - Михайлюк, В.О. (Доповіді НАН України, 2013)
При виконаннi унiкальної iгрової гiпотези (UGC) для розв’язання задачi Ins-Max-EkCSP-P (реоптимiзацiя Max-EkCSP-P при додаваннi довiльного обмеження) при k = const iснує полiномiальний оптимальний (пороговий) ψ(αZ)-наближений алгоритм, де ψ(αZ) = 2 − 1/αz i αZ — цiлочисловий розрив напiввизначеної (SDP) релаксацiї Max-EkCSP-P задачi Z.