On the complexity of the optimal transport problem with graph-structured cost.
Jiaojiao FanIsabel HaaslerJohan KarlssonYongxin ChenPublished in: CoRR (2021)
Keyphrases
- worst case
- structured data
- expected cost
- minimum cost
- dynamic programming
- optimal solution
- optimal cost
- high cost
- optimal strategy
- total cost
- spanning tree
- graph theory
- average cost
- graph structure
- directed graph
- graph representation
- decision problems
- path length
- min sum
- cost sensitive
- connected components
- closed form
- np complete
- optimal planning
- scheduling problem
- graph based algorithm