Sensitivity analysis of a greedy heuristic for knapsack problems |
| |
| Affiliation: | 1. P&QM Area, Indian Institute of Management, Vastrapur, Ahmedabad, Gujarat 380015, India;2. ORTEC Asia Pvt. Ltd., Singapore;3. Faculty of Economic Sciences, University of Groningen, Groningen, The Netherlands;1. Paris School of Economics, Université Paris 1 Panthéon-Sorbonne, CES, France;2. IPAG Business School, France;1. College of Business, Chosun University, 309 Pilmundaero, Dong-Gu, Gwangju 61452, Republic of Korea;2. College of Business, Korea Advanced Institute of Science and Technology (KAIST), 85 Hoegiro, Dongdaemun-Gu, Seoul 02455, Republic of Korea;1. Department of Economics, Ca’ Foscari University of Venice, Sestiere di Cannaregio 873, 30121 Venezia, Italy;2. Advanced School of Economics in Venice, Sestiere di Cannaregio 873, 30121 Venezia, Italy;3. Department of Management, Ca’ Foscari University of Venice, Sestiere di Cannaregio 873, 30121 Venezia, Italy;4. National Research Council-Maritime Research Centre (CNR-INSEAN), Via di Vallerano 139, 00128 Roma, Italy |
| |
| Abstract: | ![]()
In this paper, we carry out parametric analysis as well as a tolerance limit based sensitivity analysis of a greedy heuristic for two knapsack problems—the 0–1 knapsack problem and the subset sum problem. We carry out the parametric analysis based on all problem parameters. In the tolerance limit based approach, we use a definition of the sensitivity analysis problem that is polynomial for polynomial heuristics. One of the interesting and counterintuitive results described in this paper is that the tolerance limits obtained from the heuristic sensitivity analysis cannot be used as bounds for the tolerance limits of the sensitivity analysis of optimal solutions in most cases. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
