Приближенные алгоритмы, основанные на решении задачи полуопределенного программирования. $ 0.87 $-приближенный алгоритм для задачи о максимальном разрезе, раскраска вершин $ 3 $-раскрашиваемого графа в $ O(d^{0.631}) $ цветов, где $ d $ - средняя степень вершин графа.