CONSTANT-RATIO APPROXIMATION FOR ROBUST BIN PACKING WITH BUDGETED UNCERTAINTY

作     者：Bougeret, Marin Dosa, Gyorgy Goldberg, Noam Poss, Michael 

作者机构：Univ Montpellier CNRS LIRMM F-34095 Montpellier France Univ Pannonia Dept Math H-8200 Veszprem Hungary Bar Ilan Univ Dept Management IL-5290002 Ramat Gan Israel 

出 版 物：《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (SIAM J Discrete Math)

年 卷 期：2022年第36卷第4期

页      面：2534-2552页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：ANR project ROBUST [ANR-16-CE40-0018] Agence Nationale de la Recherche (ANR) [ANR-16-CE40-0018] Funding Source: Agence Nationale de la Recherche (ANR) 

主　　题：bin-packing robust optimization approximation algorithms Next-cover dynamic programming 

摘      要：We consider robust variants of the bin packing problem with uncertain item sizes. Specifically we consider two uncertainty sets previously studied in the literature. The first is budgeted uncertainty (the U-Gamma), in which at most \Gamma items deviate, each reaching its peak value, while other items assume their nominal values. The second uncertainty set, the U-Omega model, bounds the total amount of deviation in each scenario. We show that a variant of the Next-cover algorithm is a 2 approximation for the U-Omega model, and another variant of this algorithm is a 2 Gamma approximation for the U\Gamma model. Unlike the classical bin packing problem, it is shown that (unless P = NP) no asymptotic approximation scheme exists for the U-Gamma for Gamma-1. This motivates the question of the existence of a constant approximation factor algorithm for the U-Gamma model. Our main result is to answer this question by proving a (polynomial-time) 4.5 approximation algorithm, based on a dynamic-programming approach.