La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

An Approximation Algorithm for the Task-Coalition Assignment Problem Un algorithme d'approximation pour le problème d'affectation de tâches-coalition

Yoshihiro MURATA, Yasunori ISHIHARA, Minoru ITO

  • Vues en texte intégral

    0

  • Citer

Résumé:

Le problème d'affectation de tâches-coalition (TCAP) est une formalisation du problème de calcul distribué. Dans TCAP, un ensemble d'agents et un ensemble de tâches sont donnés. Un sous-ensemble d’agents traite une tâche pour produire un bénéfice. Le but du TCAP est de trouver la combinaison des tâches et des sous-ensembles d’agents qui maximise la somme des bénéfices. Dans cet article, nous définissons 1-TCAP, qui est une sous-classe pratique de TCAP. Dans 1-TCAP, les tâches et les agents sont caractérisés par des valeurs scalaires. Nous proposons un algorithme d'approximation en temps polynomial pour 1-TCAP, et montrons que cet algorithme atteint un rapport d'approximation de 9/4. Ici, un algorithme atteint un rapport d'approximation α pour un problème de maximisation si, pour chaque instance, il produit une solution de valeur au moins OPT/α, où OPT est la valeur de la solution optimale.

Publication
IEICE TRANSACTIONS on Information Vol.E85-D No.4 pp.685-693
Date de publication
2002/04/01
Publicisé
ISSN en ligne
DOI
Type de manuscrit
PAPER
Catégories
Algorithmes

Auteurs

Mots-clés

Table des matières