Zobrazeno 1 - 10
of 185
pro vyhledávání: '"Dósa, György"'
We prove new lower bounds for suitable competitive ratio measures of two relaxed online packing problems: online removable multiple knapsack, and a recently introduced online minimum peak appointment scheduling problem. The high level objective in bo
Externí odkaz:
http://arxiv.org/abs/2201.05999
Publikováno v:
In Computers and Operations Research September 2024 169
We improve the lower bound on the asymptotic competitive ratio of any online algorithm for bin packing to above 1.54278. We demonstrate for the first time the advantage of branching and the applicability of full adaptivity in the design of lower boun
Externí odkaz:
http://arxiv.org/abs/1807.05554
We consider several previously studied online variants of bin packing and prove new and improved lower bounds on the asymptotic competitive ratios for them. For that, we use a method of fully adaptive constructions. In particular, we improve the lowe
Externí odkaz:
http://arxiv.org/abs/1708.03228
We revisit the classic online bin packing problem. In this problem, items of positive sizes no larger than 1 are presented one by one to be packed into subsets called "bins" of total sizes no larger than 1, such that every item is assigned to a bin b
Externí odkaz:
http://arxiv.org/abs/1707.01728
Cardinality constrained bin packing or bin packing with cardinality constraints is a basic bin packing problem. In the online version with the parameter k \geq 2, items having sizes in (0,1] associated with them are presented one by one to be packed
Externí odkaz:
http://arxiv.org/abs/1608.06415
Publikováno v:
In Journal of Computer and System Sciences September 2020 112:34-49
Publikováno v:
In Journal of Computer and System Sciences June 2019 102:1-17
Autor:
Dósa, György, Epstein, Leah
Publikováno v:
In Journal of Computer and System Sciences September 2018 96:33-49