THE LINKING SET PROBLEM: A POLYNOMIAL SPECIAL CASE OF THE MULTIPLE-CHOICE KNAPSACK PROBLEM

摘要

We consider the linking set problem, which can be seen as a particular case of the multiple-choice knapsack problem. This problem occurs as a subproblem in a decomposition procedure for solving large-scale p-median problems such as the optimal diversity management problem. We show that if a non-increasing diference property of the costs in the linking set problem holds, then the problem can be solved by a greedy algorithm and the corresponding linear gap is null.