3
$\begingroup$

Is there any literature on approximate maximum-weight perfect matchings where the approximation criterion is not the factor between the approximate and exact weight sum achieved by each solution, but instead the cardinality of the intersection of the edge sets in the approximate and an optimal solution? The relevant class of graphs $G(V_1\cup V_2,E)$ is bipartite and assumed to have perfect matchings, i.e., $|V_1| = |V_2| = N$.

To be clear:

An $(1-\epsilon)$ approximation algorithm obtains a solution, i.e., a perfect matching $E'\subset E$, for which, for some $\epsilon > 0$, the sum of edge weights is equal or greater than $(1-\epsilon)$MWM, where MWM is the maximal sum of edge weights among all perfect matchings. Assume that $\mathcal{E}$ is the set of optimal solutions. I seek an algorithm which produces a perfect matching $E''$ satisfying $\max_{E'\in\mathcal{E}}|E''\cap E'|\geq(1-\epsilon)N$. I am willing to restrict the problem to the class of graphs for which the optimal solution is unique, and therefore the complicating term "$\max_{E'\in\mathcal{E}}$" can be removed from the problem definition.

Randomized algorithms, in the sense that 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.

$\endgroup$
  • 1
    $\begingroup$ Might be more appropriate for Theoretical Computer Science. $\endgroup$ – Yuval Filmus Jul 13 '19 at 1:27
  • $\begingroup$ Thank you. Is there a way to "migrate" the question to another forum, is is copy and paste acceptable? $\endgroup$ – prsm Jul 13 '19 at 20:12
  • $\begingroup$ Per @YuvalFilmus suggestion, this question is now asked at Theoretical Computer Science. $\endgroup$ – prsm Jul 15 '19 at 18:38
  • 4
    $\begingroup$ I'm voting to close this question as off-topic because it has been manually ported to Theoretical Computer Science. $\endgroup$ – Yuval Filmus Jul 15 '19 at 18:45