Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
An Interest-Matrix-Based Mechanism for Selfish Bin Packing
verfasst von : Xia Chen, Xin Chen, Qizhi Fang
Erschienen in: Theoretical Computer Science
Verlag: Springer Singapore
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Selfish bin packing considers a cost-sharing system of the classical bin packing problem, where each item is controlled by a selfish agent and aims to minimize the sharing cost. In this paper we study an incentive mechanism: Interest-Matrix-based (IM-based) mechanism, a new perspective that focuses on the interest or the satisfaction between any pair of items rather than personal sharing cost. Under the IM-based mechanism, we show that \(PoA\le 1.7\) for general instances with item size inside \((1/n_{0},1]\), where \(n_{0}\) is an arbitrary large integer. In special, when \(n_{0}=4\), the PoA of the IM-based mechanism does not exceed 1.5.