Bipartite Matching with Pair-Dependent Bounds

Shaul Rosner, Tami Tamir

Let $G=(U\cup V,E)$ be a bipartite graph, where $U$ represents jobs and $V$ represents machines. We study a new variant of the bipartite matching problem in which each job in $U$…