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