Асимптотические оценки эффективности локальных алгоритмов в дискретном программировании

Получены асимптотические оценки эффективности локального алгоритма для решения квазиблочных задач дискретного программирования с $n$ булевыми переменными в случае двух блоков, и показано, что асимптотическая средняя оценка эффективности локального алгоритма находится в пределах от $C_12^n/n$ до $C_22^n/n^2$ для любого алгоритма дискретного программирования, с помощью которого решаются задачи внутри блоков.