2023/02/26 by Kristóf Bérczi, Bérczi, Kristóf, Lydia Mirabel Mendoza-Cadena +3
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Matrix Theory and Algorithms #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2302.13411
openalex publication_date 2023/02/26 · openalex created_date 2023/03/03 · openalex updated_date 2026/07/28
In minimum-cost inverse optimization problems, we are given a feasible solution to an underlying optimization problem together with a linear cost function, and the goal is to modify the costs by a small deviation vector so that the input solution becomes optimal. The difference between the new and the original cost functions can be measured in several ways. In this paper, we focus on two objectives: the weighted bottleneck Hamming distance and the weighted ℓ_∞-norm. We consider a general model in which the coordinates of the deviation vector are required to fall within given lower and upper bounds. For the weighted bottleneck Hamming distance objective, we present a simple, purely combinatorial algorithm that determines an optimal deviation vector in strongly polynomial time. For the weighted ℓ_∞-norm objective, we give a min-max characterization for the optimal solution, and provide a pseudo-polynomial algorithm for finding an optimal deviation vector that runs in strongly polynomial time in the case of unit weights. For both objectives, we assume that an algorithm with the same time complexity for solving the underlying combinatorial optimization problem is available. For both objectives, we also show how to extend the results to inverse optimization problems with multiple cost functions.