New answers tagged

0

This problem is NP-hard as it can be seen by a reduction from $3$-partition. In the $3$-partition problem we are given a (multi-)set $\mathcal{S}$ containing $3n$ positive integers $x_1, \dots, x_{3n}$ and the goal is that of deciding whether there exists a partition of $\mathcal{S}$ into $n$ sets $S_1, \dots, S_n$ of $3$ elements each, such that, for each $...


1

Here is a counterexample to your proposed algorithm: The optimal solution consists of 3 edges and costs 3+1+1=5, but the min-cost maximum-cardinality matching, which consists of 2 edges and costs 3+3=6, will be chosen by the first step of your algorithm and immediately returned, as it is already a solution. (The only other maximum-cardinality matching costs ...


Top 50 recent answers are included