版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构: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.