New answers tagged

5

Set $V_i' = V_i \cap V'$. You can solve this by finding the maximum matching using at most $k$ vertices from $V_1'$ and at most $x-k$ from $V_2'$ for all $k \in [0, x]$. This in turn can be found with maximum flow. To find this maximum matching, we modify the usual reduction to maximum flow. Let $s$ be the source and $t$ the sink. Let $l$ and $r$ be ...


3

The problem is NP-hard, at least for a particular simplified configuration. Assume that each $m_l$ is effectively infinite - we can scan a particular libraries' books all on the day we get access. Let all $d_l = 1$ - each library takes one day to get access to, meaning we get access to exactly $n$ libraries. Now if $P_b = 1$ the thing that maximizes our ...


Top 50 recent answers are included