Approximation Lower Bounds in Online LIB Bin Packing and Covering
Approximation Lower Bounds in Online LIB Bin Packing and Covering
We consider the NP Hard problems of online Bin Packing and online Bin Covering While requiring that larger (or longer, in the one dimensional case) items be placed at the bottom of the bins, below smaller (or shorter) items -- we call such a version, the LIB version of problems. All bins are of unit size. In online LIB uniform-sized Bin Packing (USBP), we prove a lower bound of two on the approximation ratio for two popular heuristics belonging to the any fit class as well as the bounded space Harmonic Fit heuristic. In online LIB uniform-sized Bin Covering (USBC),it gets worse: We prove a lower bound of $\Theta(n)$ on the approximation ratio for all the heuristics mentioned above, lending credibility to a conjecture on the online USBC problem with the LIB constraint that no polynomial-time (deterministic) approximation algorithm for this problem with LIB can guarantee an AAR that is a constant, unless $P=NP$
Journal of Automata, Languages and Combinatorics, Volume 8, Number 4, 2003, 663-674
Combinatorial optimization, bin packing problem, bin covering problem, uniform sized bins, online approximation algorithm, asymptotic worst case ratio, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), longest item, Approximation methods and heuristics in mathematical programming, Approximation algorithms
Combinatorial optimization, bin packing problem, bin covering problem, uniform sized bins, online approximation algorithm, asymptotic worst case ratio, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), longest item, Approximation methods and heuristics in mathematical programming, Approximation algorithms
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!