Function graph_algo_ptas::algorithm::ptas::ptas

source · [−]
pub fn ptas(
    graph: &StableGraph<(), (), Undirected>,
    prob: &DpProblem,
    eps: f64
) -> HashSet<usize>
Expand description

Calculates an approximate solution for the given problem on the input graph. The input graph is expected to be planar.

The solution is guaranteed to be (1 - eps) optimal for maximization problems and (1 + eps) optimal for minimization problems.