Loading…
Buffer minimization with conflicts on a line
•New model for the buffer minimization with conflicts problem; Load arrives continuously.•Tight bounds on the competitive ratio for paths of various lengths.•Improved lower bound for the original model.•Algorithm for machines with speed augmentation. In the buffer minimization in multiprocessor syst...
Saved in:
Published in: | Theoretical computer science 2021-07, Vol.876, p.25-33 |
---|---|
Main Authors: | , |
Format: | Article |
Language: | English |
Subjects: | |
Citations: | Items that this one cites |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Summary: | •New model for the buffer minimization with conflicts problem; Load arrives continuously.•Tight bounds on the competitive ratio for paths of various lengths.•Improved lower bound for the original model.•Algorithm for machines with speed augmentation.
In the buffer minimization in multiprocessor systems with conflicts or simply buffer minimization problem, a multi-processor system is modelled as an undirected graph. A conflict occurs if two processors are connected by an edge. Conflicting processors can not run at the same time. At any time, load may arrive on one or more processors. Incoming workload is stored in an input buffer and a machine that is running reduces its workload at a constant rate. The goal is to find a schedule that minimizes the maximum workload over all machines and over time. We consider the special case where the graph is a path. We give upper and lower bounds on the competitive ratio for paths of various lengths. We also consider online algorithms that have resource augmentation on their speed (processing rate), and give a (1+2ε)-speed (1/ε+2)-competitive algorithm. |
---|---|
ISSN: | 0304-3975 1879-2294 |
DOI: | 10.1016/j.tcs.2021.05.013 |