Let $G$ be a bipartite graph with sides $L$ and $R.$ Let $w_{lr}$ be the edge weight of an edge from $l \in L$ to $r \in R.$ Let $x_r$ be the node weight of the node $r \in R.$ Let $E$ denote the set of all edges in $G.$ Let $2^E$ denote the set of all subsets of edges. The optimization problem is the following $$\max_{C \in 2^E}\sum_{lr \in C}w_{lr}$$ with the following constraints $$ \sum_{l: lr \in C}1 \leqslant 2 \text{ for all } r, $$ $$ \sum_{r: lr \in C}1 \leqslant 1 \text{ for all } l,$$ and $$\sum_{l:lr \in C} w_{lr} \leqslant x_r.$$

Is there any algorithm to find a solution to the above maximization problem?

In words the problem is: find the set of edges such that the sum of edge weights is maximum provided that there are at most two edges involving each $r \in R$, at most one edge involving each $l \in L,$ and the sum the edge weights for each $r \in R$ is at most the node weight of $r.$

  • $\begingroup$ It is tempting to replace each vertex $r$ with two vertices $r'$, $r''$ and replace each edge $lr$ in the original graph with the edges $lr'$, $lr''$ and then search for a maximum matching, but I don't see how to see how to enforce the last constraint. $\endgroup$ – D.W. Sep 10 '18 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.