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$

closed as off-topic by Yuval Filmus, Evil, xskxzr, D.W. Jul 16 at 6:47

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Might be more appropriate for Theoretical Computer Science. $\endgroup$ – Yuval Filmus Jul 13 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 at 20:12
  • $\begingroup$ Per @YuvalFilmus suggestion, this question is now asked at Theoretical Computer Science. $\endgroup$ – prsm Jul 15 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 at 18:45