Efficient Minimum Cost Matching Using Quadrangle Inequality

The authors present efficient algorithms for finding a minimum cost perfect matching, and for solving the transportation problem in bipartite graphs, G = (Red union Blue, Red * Blue), where mod Red mod = n, mod Blue mod = m, n >

Authors

• Alok Aggarwal
• Amotz Bar-Noy
• Samir Khuller
• Dina Kravets
• Baruch Schieber

Keywords

• Cost function
• Bipartite graph
• Transportation
• Contracts
• Computer science
• Polynomials
• Euclidean distance
• Diagonal
• Straight Line
• Less Than Or Equal
• Greater Than Or Equal
• Parallelization
• Clockwise
• Time Complexity
• Counterclockwise
• Set Of Elements
• Elements
• Perfect Match
• Left Part
• Linear Time
• Algorithm For Problem
• Total Demand
• Red Points
• Number Of Chains
• Optimal Transport