Question:
are there any algorithms, resp. what can be recommended, for calculating perfect matchings with the property that the variance of their edge's weights is minimal?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
5
If the edge weights are scaled by a sufficiently high factor, a minimum weight matching will have the least greatest weight. By also removing the edges with weight less than $w$, a minimum weight matching will give the smallest $t$ such that there is a matching with all edges in $[w,t]$.
It's past my bedtime, so I'm not sure if there is a clever way to reduce the number of rounds apart from trying all edge weights $w$.
Having woken up (sort of), I'll continue. Let $M(w)$ be the smallest $t$ such that there is a matching with weights in $[w,t]$. For particular $w$, $M(w)$ can be found as above.
Start with $m_0=M(w_0)$, where $w_0$ is the least weight of an edge. Define $w_1$ to be the weight of the lightest edge that is greater than the lightest edge of the matching that gives $M(w_0)$, and find $m_1=M(w_1)$. Define $w_2$ to be the weight of the lightest edge that is greater than the lightest edge of the matching that gives $M(w_1)$, and find $m_2=M(w_2)$. Continue in this manner until there are no matchings at all. One of the matchings you have encountered will be a matching that has the smallest range of edge weights.
In the worst case you will need to find $M(w)$ for almost every edge weight $w$, but in most cases (I think without proof) the number of minimum weight matching calculations will be much less.
Of course this answers the minimum-range version of your question. It doesn't find the least-variance matching.
answered Jun 3 at 13:39
-
$\begingroup$ One could also make an educated guess for the mean of the solution, replace every edgeweight with the squared distance from that value and the calculate the minimum weight matching with that weights; if one is bold enough he could let Brent's optimization without derivatives handle the task of finding the optimal mean. $\endgroup$ Commented Jun 3 at 16:37
-
$\begingroup$ Brent's method is for smooth functions. This objective function is piece-wise quadratic. I think it is continuous, but it isn't unimodal and I suspect it can have lots of local minima. $\endgroup$ Commented Jun 4 at 3:23
-
$\begingroup$ sorry to object, but Brent's method makes no use of derivatives, only of the unimodularity of a function, i.e. that every local minimum is also the global minimum; correct me if I'm wrong. $\endgroup$ Commented Jun 4 at 6:29
-
$\begingroup$ Brent published many methods, but there is indeed one like that. However, for this problem the function is not unimodal. $\endgroup$ Commented Jun 4 at 9:43
-
$\begingroup$ If the function isn't unimodal, the method will likely end up in a local minimum; would need some experiments to see how bad that actually gets. $\endgroup$ Commented Jun 4 at 9:50
$\begingroup$
$\endgroup$
5
A straightforward heuristic way is for each pair of edge weights $w\leq t$ present in the given graph, try to find a perfect matching in the graph restricted to the edges with weights in the interval $[w,t]$. Among those with a perfect matching, pick one with the smallest value $t-w$ (likely giving the smallest variance). To speed the things up one can do a kind of binary search over the values $t-w$.
answered Jun 3 at 10:54
-
$\begingroup$ that seems to be the only reasonable method... $\endgroup$ Commented Jun 3 at 11:01
-
$\begingroup$ I am afraid this is not going to help. The minimal variance might involve a minimal $w$ and a maximal $t$. $\endgroup$ Commented Jun 4 at 7:08
-
$\begingroup$ @ClaudeChaunier: I do not follow your point. Could you please elaborate? $\endgroup$ Commented Jun 4 at 9:55
-
$\begingroup$ A perfect matching with edge weights $1, 3, 3, 3, 3, 3, 3, 3, 3, 5$ would have variance $8$ and $t - w = 4$, while a perfect matching with edge weights $2, 2, 2, 2, 2, 4, 4, 4, 4, 4$ would have variance $10$ and $t-w = 2$. As @BrendanMcKay hinted at, the minimum-range $t-w$ method would pick the second choice instead of the better first choice. $\endgroup$ Commented Jun 5 at 9:10
-
$\begingroup$ @ClaudeChaunier: I see, thanks! For some reason I was thinking about variation rather than variance. Still, what I describe provides a heuristic (now indicated in the answer) that can do well for many practical instances. $\endgroup$ Commented Jun 5 at 14:01
$\begingroup$
$\endgroup$
This problem is polynomial-time solvable if the edge weights are small integers. I suspect this problem is weakly NP-hard, though I couldn't find NP-hardness of a similar problem.
Katoh's Algorithm
Katoh [1] provides an FPTAS for this problem. The author considers a general setting of combinatorial problems. Let $E$ be the ground set, and let $\mathscr{F} \subseteq 2^E$ denote the set of feasible solutions. Consider the following assumptions:
- Feasibility oracle: Given a subset $E' \subseteq E$, determine if $\mathscr{F} \cap 2^{E'} \neq \emptyset$.
- All solutions in $\mathscr{F}$ have the same cardinality $p$, i.e., for all $S \in \mathscr{F}$, $|S| = p$.
- For any weight assignment $c' : \mathscr{F} \rightarrow \mathbb{R}$, the linear optimization problem $\min_{S \in \mathscr{F}} \sum_{e \in S} c'(e)$ can be solved in polynomial time.
Then, there exists an $(1+\epsilon)$-approximate algorithm for the variance minimization problem with $O(|E|)$ calls to the feasibility oracle and $O(p |E| / \sqrt{\epsilon})$ calls to the linear optimization oracle.
Applying to the perfect matching, we obtain an $\tilde{O}(|V| |E|^3 / \sqrt{\epsilon})$-time algorithm. A faster implementation might be possible.
Algebraic Algorithm
An alternative pseudo-polynomial time algorithm is using the Tutte matrix. We assume all edge weights are non-negative integers at most $W$.
Then, we can determine if the graph has a perfect matching with a specific signature $(\sum_{e \in S} c(e), \sum_{e \in S} c(e)^2)$ by adapting the algebraic algorithm for the maximum matching problem [2]. The minimum variance can then be computed by checking all possible signatures.
Let $\omega$ be the matrix multiplication exponent. The algorithm runs in $\tilde{O}(|V|^{\omega} W^3)$ time with one-sided error.
References
- [1] Katoh, Naoki. "An ε-approximation scheme for combinatorial optimization problems with minimum variance criterion." Discrete applied mathematics 35.2 (1992): 131-141. https://www.sciencedirect.com/science/article/pii/0166218X9290037B
- [2] Sankowski, Piotr. "Maximum weight bipartite matching in matrix multiplication time." Theoretical Computer Science 410.44 (2009): 4480-4488. https://www.sciencedirect.com/science/article/pii/S0304397509005131
