Message Passing Algorithm for the Generalized Assignment Problem

Abstract : The generalized assignment problem (GAP) is NP-hard. It is even APX-hard to approximate it. The best known approximation algorithm is the LP-rounding algorithm in [1] with a $(1-\frac{1}{e})$ approximation ratio. We investigate the max-product belief propagation algorithm for the GAP, which is suitable for distributed implementation. The basic algorithm passes an exponential number of real-valued messages in each iteration. We show that the algorithm can be simplified so that only a linear number of real-valued messages are passed in each iteration. In particular, the computation of the messages from machines to jobs decomposes into two knapsack problems, which are also present in each iteration of the LP-rounding algorithm. The messages can be computed in parallel at each iteration. We observe that for small instances of GAP where the optimal solution can be computed, the message passing algorithm converges to the optimal solution when it is unique. We then show how to add small deterministic perturbations to ensure the uniqueness of the optimum. Finally, we prove GAP remains strongly NP-hard even if the optimum is unique.
Type de document :
Communication dans un congrès
Ching-Hsien Hsu; Xuanhua Shi; Valentina Salapura. 11th IFIP International Conference on Network and Parallel Computing (NPC), Sep 2014, Ilan, Taiwan. Springer, Lecture Notes in Computer Science, LNCS-8707, pp.423-434, 2014, Network and Parallel Computing. 〈10.1007/978-3-662-44917-2_35〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01403111
Contributeur : Hal Ifip <>
Soumis le : vendredi 25 novembre 2016 - 14:35:53
Dernière modification le : vendredi 1 décembre 2017 - 01:10:08
Document(s) archivé(s) le : mardi 21 mars 2017 - 07:34:20

Fichier

978-3-662-44917-2_35_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Mindi Yuan, Chong Jiang, Shen Li, Wei Shen, Yannis Pavlidis, et al.. Message Passing Algorithm for the Generalized Assignment Problem. Ching-Hsien Hsu; Xuanhua Shi; Valentina Salapura. 11th IFIP International Conference on Network and Parallel Computing (NPC), Sep 2014, Ilan, Taiwan. Springer, Lecture Notes in Computer Science, LNCS-8707, pp.423-434, 2014, Network and Parallel Computing. 〈10.1007/978-3-662-44917-2_35〉. 〈hal-01403111〉

Partager

Métriques

Consultations de la notice

29

Téléchargements de fichiers

51