Computational complexity on the cores of bin covering game

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.