A Dual-Fitting $\frac{3}{2}$ -Approximation Algorithm for Some Minimum-Cost Graph Problems.
James M. DavisDavid P. WilliamsonPublished in: ESA (2012)
Keyphrases
- np hard
- minimum cost
- spanning tree
- approximation ratio
- computational complexity
- undirected graph
- dynamic programming
- approximation algorithms
- network flow problem
- shortest path problem
- optimal solution
- search space
- network flow
- graph structure
- minimum cost flow
- constant factor
- lower bound
- primal dual
- objective function
- path planning
- simulated annealing
- worst case
- minimum cost path