由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - [包子求助] Graph matching problem
相关主题
问个题一道有关Graph的面试题
Zenefits Onsite 一题讨论the other problem
报个Google电面面经Interview street上的一题求助
请教一个算法关于leetcode使用方法一问
请叫大家一道题L家onsite面经
Weighted Graph Challenge 一道面试题Number of Connected Components in an Undirected Graph的follow up
问个精华区的面试题求助:什么是problem solving test?
这个问题有什么好的解法(或现成code)吗? (转载)Apple 电面
相关话题的讨论汇总
话题: problem话题: matching话题: graph话题: weighted话题: edges
进入JobHunting版参与讨论
1 (共1页)
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

1 (共1页)
进入JobHunting版参与讨论
相关主题
Apple 电面请叫大家一道题
[急]求问微软一面Weighted Graph Challenge 一道面试题
OJ挂了?问个精华区的面试题
an simple question about dynamic programming这个问题有什么好的解法(或现成code)吗? (转载)
问个题一道有关Graph的面试题
Zenefits Onsite 一题讨论the other problem
报个Google电面面经Interview street上的一题求助
请教一个算法关于leetcode使用方法一问
相关话题的讨论汇总
话题: problem话题: matching话题: graph话题: weighted话题: edges