Wasserstein Barycenters Are NP-Hard to Compute.
Jason M. AltschulerEnric Boix-AdseràPublished in: SIAM J. Math. Data Sci. (2022)
Keyphrases
- np hard
- optimal solution
- scheduling problem
- np complete
- remains np hard
- computational complexity
- np hardness
- special case
- approximation algorithms
- constraint satisfaction problems
- greedy heuristic
- pointwise
- linear programming
- lower bound
- knapsack problem
- branch and bound algorithm
- integer programming
- minimum cost
- data sets
- data mining