
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

An Approximation Algorithm for the TaskCoalition Assignment Problem
Yoshihiro MURATA Yasunori ISHIHARA Minoru ITO
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E85D
No.4
pp.685693 Publication Date: 2002/04/01 Online ISSN:
DOI: Print ISSN: 09168532 Type of Manuscript: PAPER Category: Algorithms Keyword: agent, approximation algorithm, tasks, assignment, inapproximability,
Full Text: PDF(482KB)>>
Summary:
The TaskCoalition 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 1TCAP, which is a practical subclass of TCAP. In 1TCAP, tasks and agents are characterized by scalar values. We propose a polynomialtime approximation algorithm for 1TCAP, 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.

