Под локально оптимальным деревом Штейнера понимается дерево, в котором для некоторой заданной матрицы смежности точки Штейнера размещенны оптимальным образом. Матрица смежности определяет точку локального минимума, а все допустимые для этой матрицы смежности размещения (координаты) точек Штейнера определяют окрестность минимума. Решение является локально оптимальным, если длину дерева невозможно уменьшить изменением размещения точек Штейнера. Рассмотрен алгоритм локальной оптимизиции, основанный на идее метода покоординатного спуска.
