Approximation algorithms for bipartite matching with metric and geometric costs.

Pankaj K. Agarwal R. Sharathkumar

Published in: STOC (2014)

Keyphrases

approximation algorithms
bipartite matching
minimum cost
minimum cost flow
np hard
special case
maximum weight
worst case
approximation ratio
vertex cover
randomized algorithms
constant factor
constant factor approximation
primal dual
undirected graph
combinatorial auctions
disjoint paths
np complete