Computational complexity on the cores of bin covering game
Authors: Fang, Q. and Sun, J.
Journal: PIC 2014 - Proceedings of 2014 IEEE International Conference on Progress in Informatics and Computing
Pages: 601-605
ISBN: 9781479920334
DOI: 10.1109/PIC.2014.6972405
Abstract:In this paper, we introduce a cooperative game model arising from bin covering problem, called bin covering game, and discuss the computational complexity issues on the core and the approximate core of the game. Making use of duality theorem of linear programming, a sufficient and necessary condition on core nonemptiness is proposed. When the core is empty, a lower bound on the minimum taxrate of the approximate core is obtained. Furthermore, both problems of checking membership and testing nonemptiness for the core and the approximate core of a bin covering game are proved to be NP-hard.
Source: Scopus