2018/04/21 by Florin Dobrian, Mahantesh Halappanavar, Dobrian, Florin +5
Computer Science · Economics, Econometrics and Finance · #Complexity and Algorithms in Graphs #Game Theory and Voting Systems #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.1804.08016
We consider the maximum vertex-weighted matching problem (MVM), in which\nnon-negative weights are assigned to the vertices of a graph, the weight of a\nmatching is the sum of the weights of the matched vertices, and we are required\nto compute a matching of maximum weight. We describe an exact algorithm for MVM\nwith O(|V| , |E|) time complexity, and then we design a 2/3-approximation\nalgorithm for MVM on bipartite graphs by restricting the length of augmenting\npaths to at most three. The latter algorithm has time complexity O(|E| + |V|\n\log |V|).\n The approximation algorithm solves two MVM problems on bipartite graphs, each\nwith weights only on one vertex part, and then finds a matching from these two\nmatchings using the Mendelsohn-Dulmage Theorem. The approximation ratio of the\nalgorithm is obtained by considering failed vertices, i.e., vertices that the\napproximation algorithm fails to match but the exact algorithm does. We show\nthat at every step of the algorithm there are two distinct heavier vertices\nthat we can charge each failed vertex to.\n We have implemented the 2/3-approximation algorithm for MVM and compare it\nwith four other algorithms: an exact MEM algorithm, the exact MVM algorithm, a\n1/2-approximation algorithm for MVM, and a scaling-based\n(1-\ε)-approximation algorithm for MEM. We also show that MVM problems\nshould not be first transformed to MEM problems and solved using exact\nalgorithms for the latter, since this transformation can increase runtimes by\nseveral orders of magnitude.\n