Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Min Cost Max Flow for large graphs | Reply
Has anyone implemented min cost max flow for large scale graphs with about 100k nodes that would finish working under several minutes? Standard mcmf algorithms would seem to be slow on such graph.

The graph that I need to solve the problem can be represented as bipartite graph with capacities and costs. It would have 100 nodes on the LHS and 100k nodes on the RHS with directed edges from each of the LHS nodes to each node on the RHS with capacity = 1 and certain cost. There would also be directed edges from source to each of the LHS nodes with certain capacities and zero cost and of course directed edges from all RHS nodes to the sink with capacity = 1 and cost = 0.

The original posed problem is as follows:
We have about 100 different products and up to 100k users. For each product we are given quantity in stock and for each user we know how much he/she likes each of the products. Now we would like to distribute one product to each of the users such that total happiness of users is maximized.

Edit: I stumbled upon this paper which suggests that I should take a look at LEMON library.