An Approximation Algorithm for the Task-Coalition Assignment Problem
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 社団法人電子情報通信学会の論文
- 2002-04-01
著者
-
ITO Minoru
Graduate School of Information Science, Nara Institute of Science and Technology (NAIST)
-
Ito M
Graduate School Of Information Science Nara Institute Of Science And Technology
-
MURATA Yoshihiro
Graduate School of Information Science, Nara Institute of Science and Technology
-
ISHIHARA Yasunori
Department of Informatics and Mathematical Science, Graduate School of Engineering Science
-
Ishihara Yasunori
Department Of Informatics And Mathematical Science Graduate School Of Engineering Science
-
Ito Minoru
Graduate School Of Information Science Nara Institute Of Science And Technology (naist)
-
Ito Minoru
Graduate School Of Information Science Nara Institute Of Science And Technology
-
Murata Yoshihiro
Graduate School Of Information Science Nara Institute Of Science And Technology
関連論文
- Two-layer distributed service placement method on mobile ad-hoc networks (モバイルコンピューティングとユビキタス通信)
- HDAR: Highly Distributed Adaptive Service Replication for MANETs
- Computational Complexity of Finding Meaningful Association Rules
- Implication Problems for Specialization Constraints on Databases Supporting Complex Objects
- Phlomisflavosides A and B, New Flavonol Bisglycosides from Phlomis spinidens
- An Approximation Algorithm for the Task-Coalition Assignment Problem
- A Case of Severe Hypoglycemia during Infancy Turned out to be Turner Syndrome with Ringed X
- Aromatase Inhibitor, Anastrozole, Therapy for Precocious Puberty in 3-year-old Girl with the McCune-Albright Syndrome
- A Case of Severe Hypoglycemia during Infancy Turned out to be Turner Syndrome with Ringed X
- A Female Case of Cushing's Disease with Growth Disturbance
- A Formal Approach to Detecting Security Flaws in Object-Oriented Databases (Special Issue on New Generation Database Technologies)
- An Authorization Model for Object-Oriented Databases and Its Efficient Access Control
- Complexity of the Type-Consistency Problem for Acyclic Object-Oriented Database Schemas
- Nutrient-enriched Diet in the Early Neonatal Period Influences the 3-year-old Height in Very Low Birth Weight Infants
- A Personal Navigation System with Functions to Compose Tour Schedules Based on Multiple Conflicting Criteria(Selected Papers from ICMU 2005(Second International Conference on Mobile Computing and Ubiquitous Networking))
- HDAR : Highly Distributed Adaptive Service Replication for MANETs
- Probabilistic Coverage Methods in People-Centric Sensing
- Optimum Design of ER Dampers for Ambulances
- Specialization Constraints for a Complex Object Model Supporting Selective Inheritance
- A Reinforcement Learning Method with the Inference of the Other Agent's Policy for 2-Player Stochastic Games
- A Personal Navigation System with Functions to Compose Tour Schedules Based on Multiple Conflicting Criteria
- A Personal Navigation System with Functions to Compose Tour Schedules Based on Multiple Conflicting Criteria
- Probabilistic Coverage Methods in People-Centric Sensing