t****a
发帖数: 1212 | 1 I have a graph matching problem that I want to solve. This problem involves
a weighted undirected graph and is very similar to the maximum weighted
graph matching problem http://jorisvr.nl/maximummatching.html
With respect to a weighted graph, a maximum weight matching is a matching
for which the sum of the weights of the matched edges is as large as
possible. I can find some software for solving this problem.
However, my problem is a little bit different from the standard one in that
I wish the number of selected edges in the matching is smaller than or equal
to some predetermined constant K. I want to know how to solve this problem
or if there is any approximate solution to this problem. | f*****e
发帖数: 2992 | 2 try greedy，pick the edges with the largest weights.
A little DP seems work as well.
involves
that
equal
problem
【在 t****a 的大作中提到】
: I have a graph matching problem that I want to solve. This problem involves
: a weighted undirected graph and is very similar to the maximum weighted
: graph matching problem http://jorisvr.nl/maximummatching.html
: With respect to a weighted graph, a maximum weight matching is a matching
: for which the sum of the weights of the matched edges is as large as
: possible. I can find some software for solving this problem.
: However, my problem is a little bit different from the standard one in that
: I wish the number of selected edges in the matching is smaller than or equal
: to some predetermined constant K. I want to know how to solve this problem
: or if there is any approximate solution to this problem.
| f*****e
发帖数: 2992 | 3 不是NP的问题应该有polynomial的最优解。
【在 f*****e 的大作中提到】
: try greedy，pick the edges with the largest weights.
: A little DP seems work as well.
:
: involves
: that
: equal
: problem
|
|
