Answers are grounded in this paper and cite their sources.
Classical combinatorial optimization concerns finding 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(n2 log n) time algorithm is developed, where n is the number of elements in E. Special cases with improved complexity are also discussed.
No takes yet. Share an insight, caveat, or question.
Nhan et al. (2023) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: