Skip to content

README.md

Latest commit

 

History

History
20 lines (18 loc) · 756 Bytes

README.md

File metadata and controls

20 lines (18 loc) · 756 Bytes

Approximation algorithms

Rust implmentation of various approximation algorithms:

  • Christofides algorithm
  • Double tree algorithm
  • Greedy knapsack
  • FPTAS kanpsack
  • Dynamic knapsack

Uses Blossom V algortihm from Vladimir Kolmogorov. "Blossom V: A new implementation of a minimum cost perfect matching algorithm." In Mathematical Programming Computation (MPC), July 2009, 1(1):43-67.. Source code and license may be found at /approx_algorithms/lib

Running algortihms

To run bnechmarking tests, go to Rust project folder:

cd approx_algorithms

Then run:

cargo run

This should produce benchmaking data in /dist folder, located in root directory. You may use this day to produce plots using scripts included in plot_tools