The Inverse k-Max Combinatorial Optimization Problem

Abstract

Classical combinatorial optimization problem is to find a feasible subset of a ground set in order to optimize an objective function. We address in this article the inverse optimization problem with the k-max function. In other words, we attempt to perturb the weights of elements in the ground set at minimum total cost  to make a predetermined subset optimal in the fashion of the k-max objective with respect to the perturbed weights. We first show that the problem is in general NP-hard. Regarding the case of independent feasible subsets, a combinatorial O(n^2\log n) time algorithm is developed,  where n is the number of elements in E. Special cases with improved complexity are also discussed.