Geodesic
The inverse k-max combinatorial optimization problem
Yugoslav journal of operations research, Tome 33 (2023) no. 2, p. 309

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

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 logn) time algorithm is developed, where n is the number of elements in E. Special cases with improved complexity are also discussed.
Classification : 90-08, 90B99, 90C27
Keywords: Inverse optimization, k-max, bottleneck, convex, combinatorial algorithms 
@article{YJOR_2023_33_2_a8,
     author = {Tran Hoai Ngoc Nhan and Kien Trung Nguyen and Nguyen Thanh Hung and Nguyen Thanh Toan},
     title = {The inverse k-max combinatorial optimization problem},
     journal = {Yugoslav journal of operations research},
     pages = {309 },
     publisher = {mathdoc},
     volume = {33},
     number = {2},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2023_33_2_a8/}
}
TY  - JOUR
AU  - Tran Hoai Ngoc Nhan
AU  - Kien Trung Nguyen
AU  - Nguyen Thanh Hung
AU  - Nguyen Thanh Toan
TI  - The inverse k-max combinatorial optimization problem
JO  - Yugoslav journal of operations research
PY  - 2023
SP  - 309 
VL  - 33
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/YJOR_2023_33_2_a8/
LA  - en
ID  - YJOR_2023_33_2_a8
ER  - 
%0 Journal Article
%A Tran Hoai Ngoc Nhan
%A Kien Trung Nguyen
%A Nguyen Thanh Hung
%A Nguyen Thanh Toan
%T The inverse k-max combinatorial optimization problem
%J Yugoslav journal of operations research
%D 2023
%P 309 
%V 33
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/YJOR_2023_33_2_a8/
%G en
%F YJOR_2023_33_2_a8
Tran Hoai Ngoc Nhan; Kien Trung Nguyen; Nguyen Thanh Hung; Nguyen Thanh Toan. The inverse k-max combinatorial optimization problem. Yugoslav journal of operations research, Tome 33 (2023) no. 2, p. 309 . http://geodesic.mathdoc.fr/item/YJOR_2023_33_2_a8/