pimenta's blog

By pimenta, history, 8 years ago, In English

Given a bipartite graph with nonnegative edge weights, find a matching with maximum total weight (maximum number of edges is not required).

Example:

V = {1, 2, 3, 4}, E = {{1, 2}, {3, 4}, {2, 3}}

w({1, 2}) = 1, w({3, 4}) = 1, w({2, 3}) = 10

Optimal solution: {{2, 3}}

A friend suggested the following solution:

  1. Ignore weights and find maximum cardinality bipartite matching MCBM.
  2. For each , define w'(e) = BIGVALUE - w(e).
  3. Find mincost flow for f = 1, 2, 3, ..., MCBM with respect to new weight function w'. Output the minimum.

Will that work? Is there any faster solution?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

I actually was not able to quickly find the answer to the posted question in the article posted above. Where do they discuss this problem there?

Even if it has good solution, I figured I will tell how to adjust regular min-cost max-flow to solve your problem. There are two problems here:

1, MCMF finds a flow of minimum cost, not maximum cost;

  1. MCMF first maximizes the number of edges, and only then the cost.

Consider the mincost maxflow algorithm that runs Dijkstra with potentials on each iteration to find a path to relax. We can easily solve both of the above problems with very slight adjustments:

  1. To find the flow of maximum cost instead of minimum cost it is sufficient to change edge weights with their negatives. The problem here is that Dijkstra doesn't run very well on graphs with negative weights. This problem can be easily solved by first running Bellman-Ford once, finding shortest paths to all the vertexes, and initializing potentials with those shortest paths. Now from perspective of Dijkstra all the edges are non-negative;

  2. To find the maximum cost flow, not maximum cost maximum flow (as in, to make MCMF optimize for cost instead of optimizing for flow and then for cost) just change the stopping condition to stop when the path Dijkstra finds has negative sum of weights, instead of stopping when Dijkstra can't find a path at all. It's easy to show, that each new path Dijkstra finds has smaller total weight than the previous path, so the moment you see a negative path, you will only decrease the cost after that.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    I think the first poster meant that if we complete the graph by adding edges of weight 0 where there is no edge, then the problem being solved is exactly the one solved by the Hungarian algorithm.

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 3   Vote: I like it +5 Vote: I do not like it

      I wouldn't say that he made it very clear (the fact that if you add zero-weight edges then what hungarian algorithm finds is what the OP wants). I would assume that OP knows about the hungarian algorithm, so the actual answer to his question is in your comment, not in the link above.

      I'm curious if people downvoting me exclusively because my solution is inferior to Hungarian algorithm with extra edges, or if I have some factual errors too?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    NOTE: I am not answering the question, just correcting some of your statements.

    MCMF finds a flow of minimum cost, not maximum cost

    Just multiply all costs by -1.

    MCMF first maximizes the number of edges, and only then the cost.

    Actually, given some F, MCMF can find the minimum cost for transmitting exactly F units of flow.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Just multiply all costs by -1.

      Yes, this is what I am suggesting.

      Actually, given some F, MCMF can find the minimum cost for transmitting exactly F units of flow.

      But we do not know F in advance in this particular problem.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        We can increase F by one until the shortest path in MCMF residual graph is non-negative (or does not exist).

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          That is what I'm suggesting in the original comment

          just change the stopping condition to stop when the path Dijkstra finds has negative sum of weights, instead of stopping when Dijkstra can't find a path at all