Anzeige
Erschienen in:
2020 | OriginalPaper | Buchkapitel
Parallel Online Algorithms for the Bin Packing Problem
verfasst von : Sándor P. Fekete, Jonas Grosse-Holz, Phillip Keldenich, Arne Schmidt
Erschienen in: Approximation and Online Algorithms
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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.
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.