Weighted inverse maximum perfect matching problems under the Hamming distance

Weighted inverse maximum perfect matching problems under the Hamming distance

0.00 Avg rating0 Votes
Article ID: iaor20131930
Volume: 55
Issue: 3
Start Page Number: 549
End Page Number: 557
Publication Date: Mar 2013
Journal: Journal of Global Optimization
Authors: ,
Keywords: matching, NP-hard, weights
Abstract:

Given an undirected network G(V, E, c) and a perfect matching M 0, the inverse maximum perfect matching problem is to modify the cost vector as little as possible such that the given perfect matching M 0 can form a maximum perfect matching. The modification can be measured by different norms. In this paper, we consider the weighted inverse maximum perfect matching problems under the Hamming distance, where we use the weighted Hamming distance to measure the modification of the edges. We consider both of the sum‐type and the bottleneck‐type problems. For the general case of the sum‐type case, we show it is NP‐hard. For the bottleneck‐type, we present a strongly polynomial algorithm which can be done in O(m n 3).

Reviews

Required fields are marked *. Your email address will not be published.