JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Maximum Flow tutorial Min Cost Max Flow for large graphs
 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.
 Forums Tutorial Discussions Maximum Flow tutorial Min Cost Max Flow for large graphs Previous Thread  |  Next Thread