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
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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Yoshihiro MURATA, Yasunori ISHIHARA, Minoru ITO, "An Approximation Algorithm for the Task-Coalition Assignment Problem" in IEICE TRANSACTIONS on Information,
vol. E85-D, no. 4, pp. 685-693, April 2002, doi: .
Abstract: The Task-Coalition Assignment Problem (TCAP) is a formalization of the distributed computation problem. In TCAP, a set of agents and a set of tasks are given. A subset of the agents processes a task to produce benefit. The goal of TCAP is to find the combination of the tasks and the subsets of the agents that maximizes the sum of the benefit. In this paper, we define 1-TCAP, which is a practical subclass of TCAP. In 1-TCAP, tasks and agents are characterized by scalar values. We propose a polynomial-time approximation algorithm for 1-TCAP, and show that this algorithm achieves an approximation ratio 9/4. Here, an algorithm achieves an approximation ratio α for a maximization problem if, for every instance, it produces a solution of value at least OPT/α, where OPT is the value of the optimal solution.
URL: https://global.ieice.org/en_transactions/information/10.1587/e85-d_4_685/_p
Copier
@ARTICLE{e85-d_4_685,
author={Yoshihiro MURATA, Yasunori ISHIHARA, Minoru ITO, },
journal={IEICE TRANSACTIONS on Information},
title={An Approximation Algorithm for the Task-Coalition Assignment Problem},
year={2002},
volume={E85-D},
number={4},
pages={685-693},
abstract={The Task-Coalition Assignment Problem (TCAP) is a formalization of the distributed computation problem. In TCAP, a set of agents and a set of tasks are given. A subset of the agents processes a task to produce benefit. The goal of TCAP is to find the combination of the tasks and the subsets of the agents that maximizes the sum of the benefit. In this paper, we define 1-TCAP, which is a practical subclass of TCAP. In 1-TCAP, tasks and agents are characterized by scalar values. We propose a polynomial-time approximation algorithm for 1-TCAP, and show that this algorithm achieves an approximation ratio 9/4. Here, an algorithm achieves an approximation ratio α for a maximization problem if, for every instance, it produces a solution of value at least OPT/α, where OPT is the value of the optimal solution.},
keywords={},
doi={},
ISSN={},
month={April},}
Copier
TY - JOUR
TI - An Approximation Algorithm for the Task-Coalition Assignment Problem
T2 - IEICE TRANSACTIONS on Information
SP - 685
EP - 693
AU - Yoshihiro MURATA
AU - Yasunori ISHIHARA
AU - Minoru ITO
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E85-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 2002
AB - The Task-Coalition Assignment Problem (TCAP) is a formalization of the distributed computation problem. In TCAP, a set of agents and a set of tasks are given. A subset of the agents processes a task to produce benefit. The goal of TCAP is to find the combination of the tasks and the subsets of the agents that maximizes the sum of the benefit. In this paper, we define 1-TCAP, which is a practical subclass of TCAP. In 1-TCAP, tasks and agents are characterized by scalar values. We propose a polynomial-time approximation algorithm for 1-TCAP, and show that this algorithm achieves an approximation ratio 9/4. Here, an algorithm achieves an approximation ratio α for a maximization problem if, for every instance, it produces a solution of value at least OPT/α, where OPT is the value of the optimal solution.
ER -