paminco.algo

Algorithms

The following main algorithms are implemented in paminco. While EFA computes an exact parametric minimum cost flow function for piecewise quadratic edge cost, MCA and MCFI both output a alpha-beta-approximate minimum cost flow function.

Algorithms for parametric mincost flows

Abbrev

Full name

Short summary

Source of approximation error

EFA

Electrical Flow Algorithm

Compute an optimal potential function \(\lambda \rightarrow \mathbf{\pi}(\lambda)\) for linear piecewise marginal costs that induces a parametric minimum cost function \(\lambda \rightarrow \mathbf{x}(\lambda)\).

/

MCA

Marginal Cost Approximation

Interpolate marginal edge cost and run EFA with piecewise quadratic cost .

Linear interpolation of marginal edge costs \(f_e\).

MCFI

Minimum Cost Flow Interpolation

Repeat: 1) find next parameter \(\lambda\) and 2) calculate minimum cost flow \(\mathbf{x}_{\lambda}\). Then: interpolate between breakpoint solutions.

Interpolative nature and optimizer tolerance \(\epsilon\).