k-Times Bin Packing and its Application to Fair Electricity Distribution

Dinesh Kumar Baghel, Alex Ravsky, Erel Segal-Halevi

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

Given items of different sizes and a fixed bin capacity, the bin-packing problem is to pack these items into a minimum number of bins such that the sum of item sizes in a bin does not exceed the capacity. We define a new variant called k-times bin-packing (kBP), where the goal is to pack the items such that each item appears exactly k times, in k different bins. We generalize some existing approximation algorithms for bin-packing to solve kBP, and analyze their performance ratio. The study of kBP is motivated by the problem of fair electricity distribution. In many developing countries, the total electricity demand is higher than the supply capacity. We prove that every electricity division problem can be solved by k-times bin-packing for some finite k. We also show that k-times bin-packing can be used to distribute the electricity in a fair and efficient way. Particularly, we implement generalizations of the First-Fit and First-Fit Decreasing bin-packing algorithms to solve kBP, and apply the generalizations to real electricity demand data. We show that our generalizations outperform existing heuristic solutions to the same problem. Due to space constraints, several parts of the paper were moved to appendices. All appendices are available in the full version [1].

שפה מקוריתאנגלית
כותר פרסום המארחAlgorithmic Game Theory - 17th International Symposium, SAGT 2024, Proceedings
עורכיםGuido Schäfer, Carmine Ventre
מוציא לאורSpringer Science and Business Media Deutschland GmbH
עמודים483-500
מספר עמודים18
מסת"ב (מודפס)9783031710322
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2024
אירוע17th International Symposium on Algorithmic Game Theory, SAGT 2024 - Amsterdam, הולנד
משך הזמן: 3 ספט׳ 20246 ספט׳ 2024

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך15156 LNCS
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349

כנס

כנס17th International Symposium on Algorithmic Game Theory, SAGT 2024
מדינה/אזורהולנד
עירAmsterdam
תקופה3/09/246/09/24

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'k-Times Bin Packing and its Application to Fair Electricity Distribution'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי