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 Θ(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.