Dual-ascent 2-approximation algorithm implementation for the Steiner Tree Problem. The implementation is based on papers of Wong and Pajor et al. The problem description, input format and examples can be found at the SteinLib Testdata Library.

Requirements for Unix

cmake, make, clang, libc++-dev, libc++abi-dev

Getting the test set

./get_testset.sh

Building it locally

Linux/Mac:

./build_and_test.sh

Windows:

cmake . -G "Visual Studio <version>"

where is your Visual Studio version (can be 14, 15, 16, etc.). Then open the .sln file and build the project.

Arguments

The only argument is an input file path which is required. The output file is written to <input_file>.out.

Input format

See SteinLib format description.