The linking set problem: a polynomial special case of the multiple-choice knapsack problem |
| |
Authors: | A Agra C Requejo |
| |
Institution: | 1.Departamento de Matemática,Universidade de Aveiro,Aveiro,Portugal |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|