An Approximation Algorithm for the Task-Coalition Assignment Problem

Yoshihiro MURATA  Yasunori ISHIHARA  Minoru ITO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E85-D   No.4   pp.685-693
Publication Date: 2002/04/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithms
Keyword: 
agent,  approximation algorithm,  tasks,  assignment,  inapproximability,  

Full Text: PDF(482KB)>>
Buy this Article



Summary: 
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.