咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >CONSTANT-RATIO APPROXIMATION F... 收藏

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.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分