The Knapsack Sharing Problem: An Exact Algorithm
Source: Journal of Combinatorial Optimization, Volume 6, Number 1, March 2002 , pp. 35-54(20)
Abstract:In this paper, we propose an exact algorithm for the knapsack sharing problem. The proposed algorithm seems quite efficient in the sense that it solves quickly some large problem instances. The problem is decomposed into a series of single constraint knapsack problems; and by applying the dynamic programming and another strategy, we solve optimally the original problem. The performance of the exact algorithm is evaluated on a set of medium and large problem instances (a total of 240 problem instances). This algorithm is parallelizable and this is one of its important feature.
Document Type: Regular Paper
Affiliations: 1: CERMSEM, Maison des Sciences Economiques, Université de Paris 1 Panthéon-Sorbonne, 106-112 Boulevard de l'Hôpital 75647 Paris cedex 13, France; PRiSM, Université de Versailles St-Quentin-en-Yvelines, 45 av. des Etats-Unis, 78035 Versailles Cedex, France. email@example.com 2: CERMSEM, Maison des Sciences Economiques, Université de Paris 1 Panthéon-Sorbonne, 106-112 Boulevard de l'Hôpital 75647 Paris cedex 13, France; LRI, URA 410 CNRS, Université de Paris XI, Centre d'Orsay, 91405 Orsay, France. firstname.lastname@example.org
Publication date: March 1, 2002