Opened 15 years ago
Closed 15 years ago
#314 closed enhancement (done)
Fractional matching and jumpstart initialization for general matchings
| Reported by: | Balazs Dezso | Owned by: | Balazs Dezso |
|---|---|---|---|
| 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 15 years ago by
| Attachment: | 0513ccfea967.patch added |
|---|
Changed 15 years ago by
| Attachment: | 61120524af27.patch added |
|---|
Jumpstart heuristic for fractional matching
comment:1 follow-up: 3 Changed 15 years ago by
| Status: | new → 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 15 years ago by
| Milestone: | → LEMON 1.2 release |
|---|
comment:3 follow-up: 4 Changed 15 years ago by
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 Changed 15 years ago by
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 15 years ago by
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 Changed 15 years ago by
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 15 years ago by
The patch [41d7ac528c3a] change primalScale to 2 in every fractional matching algorithms.
comment:8 follow-up: 9 Changed 15 years ago by
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 Changed 15 years ago by
| Resolution: | → done |
|---|---|
| Status: | assigned → closed |
Replying to alpar:
Replying to deba:
The patch [41d7ac528c3a] change primalScale to 2 in every fractional matching algorithms.
Is there any reason why
dualScaleis 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