Parallel Online Algorithms for the Bin Packing Problem

We study parallel online algorithms: For some fixed integer k, a collective of k parallel processes that perform online decisions on the same sequence of events forms a k-copy algorithm. For any given time and input sequence, the overall performance is determined by the best of the k individual total results. Problems of this type have been considered for online makespan minimization; they are also related to optimization with advice on future events, i.e., a number of bits available in advance. Parallel online algorithms are also of interest in practical scenarios in which redundancy is used for hedging against undesired outcomes. We develop PREDICTIVE HARMONIC(3) (PH3), a relatively simple family of k-copy algorithms for the online Bin Packing Problem, whose joint competitive factor converges to 1.5 for increasing k. In particular, we show that k = 6 suffices to guarantee a factor of 1.5714 for PH3, which is better than 1.57829, the performance of the best known 1-copy algorithm ADVANCED HARMONIC, while k = 11 suffices to achieve a factor of 1.5406, beating the known lower bound of 1.54278 for a single online algorithm. In the context of online optimization with advice, our approach implies that 4 bits suffice to achieve a factor better than this bound of 1.54278, which is considerably less than the previous bound of 15 bits.

Automated summary

The study focuses on parallel online algorithms using k parallel processes to make online decisions, where the best result is determined from k individual total results. Developed a relatively simple family of k-copy algorithms PH3 for the online Bin Packing Problem, with a competitive factor converging to 1.5 as k increases, outperforming the known algorithms.