The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Information Vol.E85-D No.4 pp.685-693

- Publication Date
- 2002/04/01

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- PAPER

- Category
- Algorithms

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.

Copy

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

Copy

@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},}

Copy

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 -