Opened 9 years ago
Closed 8 years ago
#314 closed enhancement (done)
Fractional matching and jumpstart initialization for general matchings
Reported by: | deba | Owned by: | deba |
---|---|---|---|
Priority: | major | Milestone: | LEMON 1.2 release |
Component: | core | Version: | hg main |
Keywords: | Cc: | ||
Revision id: |
Description
The fractional matching is a relaxed version of general matching algorithm if the odd set constraints are omitted from the LP formulation. It can be used to generate an initial solution of a general matching problem and in bipartite graphs it can calculate matchings directly.
Attachments (5)
Change History (14)
Changed 9 years ago by deba
comment:1 follow-up: ↓ 3 Changed 9 years ago by deba
- Status changed from new to assigned
Three patches are uploaded (they can be applied sequentially):
- The patch [0513ccfea967] contains minor changes in the matching.h.
- The patch [636dadefe1e6] contains the fractional matching algorithms, especially one push-relabel max fractional matching algorithm and two max weighted matching algorithms (perfect and non-perfect).
- The patch [61120524af27] integrates the fractional matching algorithms into the initial phase of the matching algorithms.
comment:2 Changed 9 years ago by deba
- Milestone set to LEMON 1.2 release
comment:3 in reply to: ↑ 1 ; follow-up: ↓ 4 Changed 9 years ago by alpar
Replying to deba:
Three patches are uploaded (they can be applied sequentially):
- The patch [0513ccfea967] contains minor changes in the matching.h.
Looking at the diff it is far from being minor.
What does the sentence
"The solved problems did not cause wrong solution."
mean in the commit log?
comment:4 in reply to: ↑ 3 Changed 9 years ago by deba
Replying to alpar:
Replying to deba:
Three patches are uploaded (they can be applied sequentially):
- The patch [0513ccfea967] contains minor changes in the matching.h.
Looking at the diff it is far from being minor.
What does the sentence
"The solved problems did not cause wrong solution."
mean in the commit log?
The patch does not solve bug, it just improve and simplify the matching implementation.
comment:5 follow-up: ↓ 6 Changed 8 years ago by alpar
The implementation is based on extensive use of priority queues and provides $O(nm\log n)$ time complexity.
This text appears both at the doc of the Edmonds weighted matching algs and also in the doc of fractional mathcing algs. I doubt it is correct at both places.
Also, a strange /// appears in the doc of the fractional matching algs.
Finally, the doc says
If the value type is integer, then the primal and the dual solutions are multiplied by 2 and 4 respectively.
Firstly, I guess it is in order to ensure that the solutions are also integer. However it makes the results a bit inconsistent. What about also multiplying the values in the floating point cases?
Secondly, the "4" in the text became a link somehow, which is quite strange.
comment:6 in reply to: ↑ 5 Changed 8 years ago by deba
Replying to alpar:
I have fixed some of the mentioned issues in [86613aa28a0c].
The implementation is based on extensive use of priority queues and provides $O(nm\log n)$ time complexity.
This text appears both at the doc of the Edmonds weighted matching algs and also in the doc of fractional mathcing algs. I doubt it is correct at both places.
Both algorithms are using priority queues, but maybe this is not so special for fractional matching algorithms.
Also, a strange /// appears in the doc of the fractional matching algs.
It is fixed.
Finally, the doc says
If the value type is integer, then the primal and the dual solutions are multiplied by 2 and 4 respectively.
Firstly, I guess it is in order to ensure that the solutions are also integer. However it makes the results a bit inconsistent. What about also multiplying the values in the floating point cases?
It can be a reasonable option.
Secondly, the "4" in the text became a link somehow, which is quite strange.
It is intended, but I wanted to make link also from 2. They must refer to the static const int members of primalScale and dualScale.
comment:7 follow-up: ↓ 8 Changed 8 years ago by deba
The patch [41d7ac528c3a] change primalScale to 2 in every fractional matching algorithms.
comment:8 in reply to: ↑ 7 ; follow-up: ↓ 9 Changed 8 years ago by alpar
Replying to deba:
The patch [41d7ac528c3a] change primalScale to 2 in every fractional matching algorithms.
Is there any reason why dualScale is still different for integer vs. floating point values?
comment:9 in reply to: ↑ 8 Changed 8 years ago by alpar
- Resolution set to done
- Status changed from assigned to closed
Replying to alpar:
Replying to deba:
The patch [41d7ac528c3a] change primalScale to 2 in every fractional matching algorithms.
Is there any reason why dualScale is still different for integer vs. floating point values?
Alas, we did the same in the matching classes (which have already been released in branch 1.1), thus we need it for the coherence with those classes.
As of [d8ea85825e02], all the changesets are in main brain.
Improvements in matching.h