Inverse version of the kth maximization combinatorial optimization problem

Abstract

Given a ground set of n elements with associated positive weights and a class of its subsets, also known as feasible solutions. In the setting of the original combinatorial optimization problem, each feasible solution corresponds to an objective value, often measured under the sum or the max of all element weights in the underlying solution. We address in this paper the problem of modifying the weight of elements in the ground set such that a prespecified subset becomes the k-th maximizer with respect to new weights and the cost is minimized. This problem is called the inverse version of the k-th maximization combinatorial optimization. We propose two quadratic that solve this problem with sum objective function under Chebyshev norm and the bottleneck Hamming distance. Additionally, if the objective function is the max function then this problem can be solved in O(n^2 logn) time.