Лагранжевая оценка для максимального разреза графа с заданными количествами вершин в обоих подмножествах разбиения

Abstract

The problem of finding upper Lagrange bound Ψ* for quadratic formulation of maximum cut problem with given numbers of vertices in both partition subsets is considered. It's shown that finding Ψ* reduce to solving unconstraint problem of minimizing convex function.