I have asked this question in cs.stackeschange, and it was recommended to me that I asked it here.

Is there any literature on approximate maximum-weight perfect matchings where the approximation criterion is not a factor between the weight sum of the approximate and the optimal solutions, but instead the cardinality of the intersection of the edge sets of the approximate and the optimal solutions to the original maximum-weight perfect matching? The relevant graphs $G(V_1\cup V_2,E)$, $V_1\cap V_2=\varnothing$, are bipartite with non-negative possibly non-uniform edge weights and assumed to have perfect matchings. In particular, $|V_1| = |V_2|$.

To be clear:

Let $\mathcal{G}$ the the class of graphs $G$ as above, and let $\mathcal{E}_{G}$ be the set of maximum-weight perfect matchings of a $G\in\mathcal{G}$ with $|V_1| = N$. I seek an approximation algorithm which outputs a perfect matching $E''$ of $G$ satisfying $\max_{E'\in\mathcal{E}_{G}}|E''\cap E'|\geq(1-\epsilon)N$.

If it helps, I am willing to restrict the problem to the class of graphs for which $|\mathcal{E}_{G}|=1$, and therefore the potentially complicating term "$\max_{E'\in\mathcal{E}_{G}}$" can be removed from the problem definition. Randomized algorithms, in the sense that their output satisfies the required inequality with probability $1 - \delta$, for some $\delta > 0$, are also welcome.

I am familiar with Duan and Pettie's work, and most references therein.

  • $\begingroup$ Yes, my input graph has non-negative possibly non-uniform edge weights. The algorithm I seek should, as stated in both paragraphs, satisfy criterion (i). The second and admittedly confusing paragraph describes two criteria, but criterion (ii) is presented only to contrast the solutions found by the approximation algorithms I found in the literature (e.g., those in and referred by Duan and Pettie) with the one I am looking for. Indeed, Duan and Pettie's contribution does not apply to perfect matchings, but some of the references therein do. Do these confusions warrant an editing? $\endgroup$ – prsm Jul 15 '19 at 18:25
  • $\begingroup$ Weight must be mentioned. I am looking for approximations which are themselves perfect matchings and for which the approximation criterion is the number of intersections between the approximate and maximum-weight perfect matchings. $\endgroup$ – prsm Jul 16 '19 at 16:31
  • $\begingroup$ FYI a similar question has been studied for NP-complete problems. E.g. see references in this paper. $\endgroup$ – Neal Young Jul 16 '19 at 16:54
  • $\begingroup$ I've only skimmed through the reference, but it is indeed relevant to the question. It has already led me to consider a small reformulation where, without loss of generality, the requirement is that $|E''\cap E'|\geq (1-\epsilon)N$ for some $E'\in\mathcal{E}_{G}$, without the "$\max_{E'\in\mathcal{E}_{G}}$" term. $\endgroup$ – prsm Jul 16 '19 at 21:24
  • $\begingroup$ The reference also forces me to make explicit that I am looking for an efficient algorithm in some yet-to-be-specified sense, since, in contrast to 3-SAT, there are known polynomial-time exact algorithms for the maximum-weight bipartite perfect matching, any of which would be a positive answer to my question. $\endgroup$ – prsm Jul 16 '19 at 21:25

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.