Title :
An allocation algorithm of indivisible goods
Author :
Shimizu, Kohei ; Manabe, Yoshifumi
Author_Institution :
Dept. of Inf., Kogakuin Univ., Tokyo, Japan
Abstract :
This paper proposes a new allocation algorithm of indivisible goods. We consider the case when the total value of the whole goods is the same for every participant, which models allocation at divorce or inheritance. The worst participant´s obtained value must be maximized. There are not good allocation algorithms for our rating scale. We show that this problem is NP-complete. Therefore we propose four types of approximation algorithms. Among the four algorithms, the raising standard algorithm has the best ratio that the algorithm outputs the optimal solution by a computer simulation.
Keywords :
approximation theory; optimisation; resource allocation; set theory; NP-complete problem; approximation algorithms; computer simulation; indivisible goods allocation algorithm; rating scale; Approximation algorithms; Approximation methods; Communications technology; Computer simulation; Partitioning algorithms; Resource management; Standards;
Conference_Titel :
Information and Telecommunication Technologies (APSITT), 2015 10th Asia-Pacific Symposium on
Conference_Location :
Colombo
DOI :
10.1109/APSITT.2015.7217090