<p>I have asked this question in <a href="https://cs.stackexchange.com/questions/111766/alternative-criterion-for-approximate-maximum-weight-perfect-matching-algorithms">cs.stackeschange</a>, and it was recommended to me that I asked it here.</p>

<p>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 <span class="math-container">$G(V_1\cup V_2,E)$</span>, <span class="math-container">$V_1\cap V_2=\varnothing$</span>, are bipartite with non-negative possibly non-uniform edge weights and assumed to have perfect matchings. In particular, <span class="math-container">$|V_1| = |V_2|$</span>.</p>

<p>To be clear:</p>

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

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

<p>I am familiar with <a href="https://web.eecs.umich.edu/~pettie/papers/ApproxMWM-JACM.pdf" rel="nofollow noreferrer">Duan and Pettie's work</a>, and most references therein.</p>

CC BY-SA 4.0
2019-07-15T18:25:55.880Z
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?
prsm
CC BY-SA 4.0
2019-07-16T16:31:03.770Z
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.
prsm
CC BY-SA 4.0
2019-07-16T16:54:36.313Z
FYI a similar question has been studied for NP-complete problems.  E.g. see references in [this paper](http://dx.doi.org/10.4086/toc.2013.v009a022).
Neal Young
CC BY-SA 4.0
2019-07-16T21:24:16.063Z
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.
prsm
CC BY-SA 4.0
2019-07-16T21:25:59.580Z
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.
prsm
CC BY-SA 4.0
2019-07-16T23:21:24.600Z
I'd like to pose a variant of the question asking for known results on statistics of $\max_{E'\in\mathcal{E}_{G}}|E''\cap E'|$. Should I write a new post? From the feedback I've received so far I'd assume the answer is yes.
prsm
CC BY-SA 4.0
2019-07-17T13:00:48.443Z
Your problem reduces to finding a max-weight perfect matching in the given bipartite graph.  On the other hand, the restriction of your problem to instances where all edges have weight 1 is equivalent to the assignment problem (finding a perfect matching in a given bipartite graph).  So your problem lies (in difficulty) between these two problems.  Per your linked reference, the fastest known algorithms for these two problem take $O(m\sqrt n)$ and $O(m\sqrt n \log (nN))$ time, where $N$ is the max edge weight (assuming edge weights are integers), the same up to a logarithmic factor...
Neal Young
<approximation-algorithms><randomized-algorithms><matching><bipartite-graphs>
Alternative criterion for approximate maximum-weight perfect matching algorithms
prsm
# Alternative criterion for approximate maximum-weight perfect matching algorithms

(Asked by: username_0 on 2019-07-15)

I have asked this question in [cs.stackeschange](https://cs.stackexchange.com/questions/111766/alternative-criterion-for-approximate-maximum-weight-perfect-matching-algorithms), 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](https://web.eecs.umich.edu/~pettie/papers/ApproxMWM-JACM.pdf), and most references therein.

**Tags:** approximation-algorithms, randomized-algorithms, matching, bipartite-graphs

> **Comments:**
> **username_0**: 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?  
> **username_0**: 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.  
> **username_1**: FYI a similar question has been studied for NP-complete problems.  E.g. see references in [this paper](http://dx.doi.org/10.4086/toc.2013.v009a022).  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_0**: I'd like to pose a variant of the question asking for known results on statistics of $\max_{E'\in\mathcal{E}_{G}}|E''\cap E'|$. Should I write a new post? From the feedback I've received so far I'd assume the answer is yes.  
> **username_1**: Your problem reduces to finding a max-weight perfect matching in the given bipartite graph.  On the other hand, the restriction of your problem to instances where all edges have weight 1 is equivalent to the assignment problem (finding a perfect matching in a given bipartite graph).  So your problem lies (in difficulty) between these two problems.  Per your linked reference, the fastest known algorithms for these two problem take $O(m\sqrt n)$ and $O(m\sqrt n \log (nN))$ time, where $N$ is the max edge weight (assuming edge weights are integers), the same up to a logarithmic factor...  

---

## 0 answers

