Nonlinear Bipartite Matching
Yael Berstein, Shmuel Onn · arXiv (Cornell University) · 2006
We study the problem of optimizing nonlinear objective functions over bipartite matchings. While the problem is generally intractable, we provide several efficient algorithms for it, including a deterministic algorithm for maximizing convex objectives, approximative algorithms for norm minimization and maximization, and a randomized algorithm for optimizing arbitrary objectives.