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


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

The data on this page was last updated at 16:12 on May 5, 2021.