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/