Dósa György and Epstein Leah: The convergence time for selfish bin packing. In: Acta cybernetica, (23) 3. pp. 853-866. (2018)
Preview |
Cikk, tanulmány, mű
actacyb_23_3_2018_08.pdf Download (354kB) | Preview |
Abstract
In classic bin packing, the objective is to partition a set of n items with positive rational sizes in (0, 1] into a minimum number of subsets called bins, such that the total size of the items of each bin at most 1. We study a bin packing game where the cost of each bin is 1, and given a valid packing of the items, each item has a cost associated with it, such that the items that are packed into a bin share its cost equally. We find tight bounds on the exact worst-case number of steps in processes of convergence to pure Nash equilibria. Those are processes that are given an arbitrary packing as an initial packing. As long as there exists an item that can reduce its cost by moving from its bin to another bin, in each step, a controller selects such an item and instructs it to perform such a beneficial move. The process converges when no further beneficial moves exist. The tight function of n that we find is in Θ(n 3/2 ). This improves the previous bound of Ma et al. [14], who showed an upper bound of O(n 2).
| Item Type: | Article |
|---|---|
| Journal or Publication Title: | Acta cybernetica |
| Date: | 2018 |
| Volume: | 23 |
| Number: | 3 |
| ISSN: | 0324-721X |
| Page Range: | pp. 853-866 |
| Language: | English |
| Place of Publication: | Szeged |
| Related URLs: | http://acta.bibl.u-szeged.hu/55467/ |
| Uncontrolled Keywords: | Konvergencia, Matematika |
| Additional Information: | Bibliogr.: p. 864-865. ; összefoglalás angol nyelven |
| Subjects: | 01. Natural sciences 01. Natural sciences > 01.02. Computer and information sciences |
| Date Deposited: | 2018. Nov. 08. 08:34 |
| Last Modified: | 2022. Jun. 21. 08:15 |
| URI: | http://acta.bibl.u-szeged.hu/id/eprint/55681 |
Actions (login required)
 |
View Item |
