Convex Matroid Optimization
- Author(s): Onn, Shmuel;
- et al.
Published Web Locationhttps://arxiv.org/pdf/math/0207136.pdf
We consider a problem of optimizing convex functionals over matroid bases. It is richly expressive and captures certain quadratic assignment and clustering problems. While generally NP-hard, we show it is polynomial time solvable when a suitable parameter is restricted.