Oct. 28, 2024, 11:43 a.m.
Better understanding the Steiner Tree
The work of Jarosław Byrka, Fabrizio Grandoni, and Vera Traub The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2 has been accepted at FOCS’24 – one of the most prestigious computer science conferences in the world.
Advances in Understanding the Steiner Tree
One of the classic optimization problems is: How can we most cheaply connect a given subset of vertices in a graph? Linear programs, which model the selection of an appropriate subset of edges, help in finding the best possible solutions.
The simplest of them, UCR (Undirected Cut Relaxation), simply has edge variables and is known to be weak (as a method of estimating the cost of an optimal solution). The strongest, HYP (Hypergraphic), with variables on subsets of vertices to be connected, is more accurate but impractical due to the very large number of variables. The hope lies in an intermediate program, BCR (Bidirected Cut Relaxation), with variables on directed edges, which is fast but has an unknown degree of accuracy.
In collaboration with Prof. Fabrizio Grandoni (Lugano, Switzerland) and Prof. Vera Traub (Bonn, Germany), we have, for the first time, shown that BCR is significantly stronger than UCR. This discovery raises hope that efficient primal-dual algorithms based on BCR may be developed in the future.