The Inverse k-Max Combinatorial Optimization Problem

  • Tran Hoai Ngoc Nhan Faculty of Basic Sciences, Vinh Long University of Technology Education, Vinh Long, Vietnam
  • Kien Trung Nguyen Department of Mathematics, Teacher College, Can Tho University, Can Tho, Vietnam
  • Nguyen Thanh Hung Can Tho University
  • Nguyen Thanh Toan Faculty of Mathematics and Computer Science, University of Science, Ho Chi Minh City, Vietnam; Vietnam National University, Ho Chi Minh City, Vietnam; Faculty of Basic Sciences, Vinh Long University of Technology Education, Vinh Long, Vietnam

Abstract

Classical combinatorial optimization problem is to find 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(n^2\log n) time algorithm is developed,  where n is the number of elements in E. Special cases with improved complexity are also discussed.

Published
Dec 28, 2022
How to Cite
NHAN, Tran Hoai Ngoc et al. The Inverse k-Max Combinatorial Optimization Problem. Yugoslav Journal of Operations Research, [S.l.], v. 33, n. 2, p. 309–322, dec. 2022. ISSN 2334-6043. Available at: <http://yujor.fon.bg.ac.rs/index.php/yujor/article/view/1119>. Date accessed: 22 may 2024. doi: http://dx.doi.org/10.2298/YJOR220516037N.
Section
Research Articles