Return to Question

Last month I discovered a nice question on stackoverflow and thought the 1,n matching problem could be solved via introducing a 1,k tree matching. Look here for my question, but as Moron pointed out this is not known to be solvable in polynomial time.

Now I discovered mathoverflow and would like to know if one could reduce some possibilities or if one could introduce some restrictions so that the 1,n matching could be solved in polytime. Do you have an idea?

Background: I would like to implement a heuristic for that problem. At the moment I am using an algorithm based on the GPA heuristic for weighted maximum matchings in general graphs as described here.

Here is my formulation of the problem:

Instead of the 'normal' "one-to-one" matching in a bipartite graph I want to calculate the maximum "one-to-many" matching for a bipartite graph G. (Should I define it or is this clear?)
For the initial problem 1:n the n was arbitrary. Then I fixed the n to k 'static' choices via trees instead of edges, but this was hard, too.
Now I would like to find a similar graph or different formulation which is solvable in polytime (or at least there should be a high accurate and 'fast' algorithm). E.g. couldn't I apply the polytime matching algorithm from general graphs and apply it to a slightly changed graph G'? I think about the following graph G':

http://karussell.files.wordpress.com/2010/03/network2.png (don't have rep to include it here :-/)

Clearly there are matchings (red) in the general graph G' which could result in strange/wrong matchings for the corresponding bipartite matching in the bipartite graph G. But maybe one could further tweak the graph G' or the edge weights of G'?

Or how is this related to hypergraphs (e.g. if edge would have 3 nodes)

Last month I discovered a nice question on stackoverflow and thought the 1,n matching problem could be solved via introducing a 1,k tree matching. Look here for my question, but as Moron pointed out this is not known to be solvable in polynomial time.

Now I discovered mathoverflow and would like to know if one could reduce some possibilities or if one could introduce some restrictions so that the 1,n matching could be solved in polytime. Do you have an idea?

Background: I would like to implement a heuristic for that problem. At the moment I am using an algorithm based on the GPA heuristic for weighted maximum matchings in general graphs as described here (broken link).

Here is my formulation of the problem:

Instead of the 'normal' "one-to-one" matching in a bipartite graph I want to calculate the maximum "one-to-many" matching for a bipartite graph G. (Should I define it or is this clear?) For the initial problem 1:n the n was arbitrary. Then I fixed the n to k 'static' choices via trees instead of edges, but this was hard, too.

Now I would like to find a similar graph or different formulation which is solvable in polytime (or at least there should be a high accurate and 'fast' algorithm). E.g. couldn't I apply the polytime matching algorithm from general graphs and apply it to a slightly changed graph G'? I think about the following graph G':

     ^(source)

Clearly there are matchings (red) in the general graph G' which could result in strange/wrong matchings for the corresponding bipartite matching in the bipartite graph G. But maybe one could further tweak the graph G' or the edge weights of G'?

Or how is this related to hypergraphs (e.g. if edge would have 3 nodes)

Last month I discovered a nice question on stackoverflow and thought the 1,n matching problem could be solved via introducing a 1,k tree matching. Look here for my question, but as Moron pointed out this is not known to be solvable in polynomial time.

Now I discovered mathoverflow and would like to know if one could reduce some possibilities or if one could introduce some restrictions so that the 1,n matching could be solved in polytime. Do you have an idea?

Background: I would like to implement a heuristic for that problem. At the moment I am using an algorithm based on the GPA heuristic for weighted maximum matchings in general graphs as described here.

Here is my formulation of the problem:

Instead of the 'normal' "one-to-one" matching in a bipartite graph I want to calculate the maximum "one-to-many" matching for a bipartite graph G. (Should I define it or is this clear?)
For the initial problem 1:n the n was arbitrary. Then I fixed the n to k 'static' choices via trees instead of edges, but this was hard, too.
Now I would like to find a similar graph or different formulation which is solvable in polytime (or at least there should be a high accurate and 'fast' algorithm). E.g. couldn't I apply the polytime matching algorithm from general graphs and apply it to a slightly changed graph G'? I think about the following graph G':

http://karussell.files.wordpress.com/2010/03/network2.png (don't have rep to include it here :-/)

Clearly there are matchings (red) in the general graph G' which could result in strange/wrong matchings for the corresponding bipartite matching in the bipartite graph G. But maybe one could further tweak the graph G' or the edge weights of G'?

Or how is this related to hypergraphs (e.g. if edge would have 3 nodes)

Missing tag: matching

Last month I discovered a nice question on stackoverflow and thought the 1,n matching problem could be solved via introducing a 1,k tree matching. Look here for my question, but as Moron pointed out this is not known to be solvable in polynomial time.

Now I discovered mathoverflow and would like to know if one could reduce some possibilities or if one could introduce some restrictions so that the 1,n matching could be solved in polytime. Do you have an idea?

Background: I would like to implement a heuristic for that problem. At the moment I am using an algorithm based on the GPA heuristic for weighted maximum matchings in general graphs as described here.

Here is my formulation of the problem:

Instead of the 'normal' "one-to-one" matching in a bipartite graph I want to calculate the maximum "one-to-many" matching for a bipartite graph G. (Should I define it or is this clear?)
For the initial problem 1:n the n was arbitrary. Then I fixed the n to k 'static' choices via trees instead of edges, but this was hard, too.
Now I would like to find a similar graph or different formulation which is solvable in polytime (or at least there should be a high accurate and 'fast' algorithm). E.g. couldn't I apply the polytime matching algorithm from general graphs and apply it to a slightly changed graph G'? I think about the following graph G':

http://karussell.files.wordpress.com/2010/03/network2.png (don't have rep to include it here :-/)

Clearly there are matchings (red) in the general graph G' which could result in strange/wrong matchings for the corresponding bipartite matching in the bipartite graph G. But maybe one could further tweak the graph G' or the edge weights of G'?

Or how is this related to hypergraphs (e.g. if edge would have 3 nodes)

Last month I discovered a nice question on stackoverflow and thought the 1,n matching problem could be solved via introducing a 1,k tree matching. Look here for my question, but as Moron pointed out this is not known to be solvable in polynomial time.

Now I discovered mathoverflow and would like to know if one could reduce some possibilities or if one could introduce some restrictions so that the 1,n matching could be solved in polytime. Do you have an idea?

Background: I would like to implement a heuristic for that problem. At the moment I am using an algorithm based on the GPA heuristic for weighted maximum matchings in general graphs as described here.

Here is my formulation of the problem:

Instead of the 'normal' "one-to-one" matching in a bipartite graph I want to calculate the maximum "one-to-many" matching for a bipartite graph G. (Should I define it or is this clear?)
For the initial problem 1:n the n was arbitrary. Then I fixed the n to k 'static' choices via trees instead of edges, but this was hard, too.
Now I would like to find a similar graph or different formulation which is solvable in polytime (or at least there should be a high accurate and 'fast' algorithm). E.g. couldn't I apply the polytime matching algorithm from general graphs and apply it to a slightly changed graph G'? I think about the following graph G':

http://karussell.files.wordpress.com/2010/03/network2.png (don't have rep to include it here :-/)

Clearly there are matchings (red) in the general graph G' which could result in strange/wrong matchings for the corresponding bipartite matching in the bipartite graph G. But maybe one could further tweak the graph G' or the edge weights of G'?

Or how is this related to hypergraphs (e.g. if edge would have 3 nodes)

Missing tag: matching

Last month I discovered a nice question on stackoverflow and thought the 1,n matching problem could be solved via introducing a 1,k tree matching. Look here for my question, but as Moron pointed out this is not known to be solvable in polynomial time.

Now I discovered mathoverflow and would like to know if one could reduce some possibilities or if one could introduce some restrictions so that the 1,n matching could be solved in polytime. Do you have an idea?

Background: I would like to implement a heuristic for that problem. At the moment I am using an algorithm based on the GPA heuristic for weighted maximum matchings in general graphs as described here.

Here is my formulation of the problem:

Instead of the 'normal' "one-to-one" matching in a bipartite graph I want to calculate the maximum "one-to-many" matching for a bipartite graph G. (Should I define it or is this clear?)
For the initial problem 1:n the n was arbitrary. Then I fixed the n to k 'static' choices via trees instead of edges, but this was hard, too.
Now I would like to find a similar graph or different formulation which is solvable in polytime (or at least there should be a high accurate and 'fast' algorithm). E.g. couldn't I apply the polytime matching algorithm from general graphs and apply it to a slightly changed graph G'? I think about the following graph G':

http://karussell.files.wordpress.com/2010/03/network2.png (don't have rep to include it here :-/)

Clearly there are matchings (red) in the general graph G' which could result in strange/wrong matchings for the corresponding bipartite matching in the bipartite graph G. But maybe one could further tweak the graph G' or the edge weights of G'?

Or how is this related to hypergraphs (e.g. if edge would have 3 nodes)

Missing tag: matching