分散計算問題の定式化の一つとして，仕事に対するエージェント集合割り 当て問題 (Task-Coalition Assignment Problem，以下TCAP)がある． TCAPでは，エージェントと仕事がそれぞれ複数与えられ， 仕事をエージェント集合が処理することによって利益が得られる． この利益を最大化するエージェント集合と仕事の組み合せを求める のが目的である．
本発表ではまず，TCAPを厳密に定義する． そして最大クリーク問題がTCAPの 特別な場合であることを示すことにより，P=NPでない限り最適解の値と近似解 の値の比が定数であるような多項式時間アルゴリズムが存在しないことを 証明する． 次に，実用的なTCAPのサブクラスである1-TCAPを定義する．1-TCAPでは エージェントと仕事がスカラー量で特徴づけられる．本稿では1-TCAPに対する 近似アルゴリズムを示し，最適解の値と近似解 の値の比が最悪の場合でも3以下であることを証明する．