The Buffer Minimization Problem for Scheduling Flow Jobs with Conflicts

Niklas Haas, Sören Schmitt, Rob van Stee · 2025

Read The Buffer Minimization Problem for Scheduling Flow Jobs with Conflicts by Niklas Haas, Sören Schmitt, Rob van Stee (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-19690.txt.

Introduction

Niklas Haas, Sören Schmitt, and Rob van Stee study an online scheduling problem where processors conflict with each other. Jobs flow into buffers on processors over time, and running processors drain them, but conflicting pairs cannot run at once. Conflicts form a graph, and the goal is to keep the largest buffer load as small as possible.

Unlike the older model, work arrives continuously over intervals rather than in blocks at set times. The authors give tight bounds for every graph on four vertices except the path, which was already solved, and for complete and complete bipartite graphs. Almost tight bounds cover general graphs as well.

Catalog record

CREATORNiklas Haas, Sören Schmitt, Rob van Stee
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-19690

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Buffer Minimization Problem for Scheduling Flow Jobs with Conflicts Niklas Haas, Sören Schmitt, Rob van Stee Abstract We consider the online buffer minimization in multiprocessor systems with conflicts problem (in short, the buffer minimization problem ) in the recently introduced flow model. In an online fashion, workloads arrive on some of the n n processors and are stored in an input buffer. Processors can run and reduce these workloads, but conflicts between pairs of processors restrict simultaneous task execution. Conflicts are represented by a graph, where vertices correspond to processors and edges indicate conflicting pairs. An online algorithm must decide which processors are run at a time; so provide a valid schedule respecting the conflict constraints. The objective is to minimize the maximal workload observed across all processors during the schedule. Unlike the original model, where workloads arrive as discrete blocks at specific time points, the flow model assumes workloads arrive continuously over intervals or not at all. We present tight bounds for all graphs with four vertices (except the path, which has been solved previously) and for the families of general complete graphs and complete bipartite graphs. We also recover almost tight bounds for complete k k -partite graphs. For the original model, we narrow the gap for the graph consisting of a triangle and an additional edge to a fourth vertex. 1 Introduction In practical multiprocessor settings, it often happens that processors (also called machines) share resources. In such cases, only one of these machines can use the resource at any given time. We model such a situation using a conflict graph which specifies for the given set of machines, which are the vertices of the graph, which pairs of machines share resources. This is indicated by having an edge between two machines. We consider a model with m parallel machines. Load arrives over time, separately to each of the machines. Time is continuous. Each machine has a buffer to store unprocessed load. If a machine is running, it processes load at a rate of 1. A machine can only run if none of the machines with which it has a conflict (that is, its neighbors in the conflict graph) is running. The goal is to minimize the maximum load that is ever stored in a single buffer. We consider the online setting in which the future arriving load is unknown. An online algorithm is compared to the optimal offline solution that can only be achieved if the whole input is known in advance. Note that in the optimal solution, buffers are often also required: consider two neighboring machines that receive load at the same time. The question now becomes: what size buffers does an online algorithm need, relative to the buffer size in an optimal solution, so that the online algorithm can process any input without overflowing any buffer? This number is known as the competitive ratio, and it depends on the conflict graph and on the number of machines. Chrobak et al. [ 7 ] who introduced this model considered two versions: one where the online algorithm knows the optimal buffer size in advance (the weak competitive ratio) and one where it does not (the strong competitive ratio). In this paper, we will focus on the first measure, which we will usually call simply competitive ratio . In the original model, load arrives as discrete tasks of various sizes. Höhne and van Stee [ 11 ] later introduced the so-called flow model in which at all times, for any machine, load either arrives at a constant rate of 1 (not as an instantaneous block of load) or not at all. The model is a special case of the original model which maintains its overall complexity. An interesting feature of the flow model is that deterministic algorithms appear to be as powerful as randomized algorithms (against an oblivious adversary). Previously only complete ( k -partite) graphs and paths have been considered. We go the next natural step and focus on graphs with four vertices. Our goal is to investigate which factors contribute to the problem’s difficulty. In this paper, we consider all graphs with at most four vertices and give tight results for the flow model in all cases. We also give tight or nearly tight results for larger graphs, as well as tight results for almost all graphs with four vertices in the original model. All of our algorithms are short to state, but are carefully constructed to handle various difficult inputs. The proofs involve intricate considerations of what combinations of delays are possible on the various machines. A main building block of the proof consists of invariants for the total delay on pairs or triples of adjacent machines. 1.1 Related Work The buffer minimization in multiprocessor systems with conflicts problem was introduced by Chrobak et al. in 2001 [ 7 ] . They present a universal algorithm showing that even the strong competitive ratio on any graph is bounded. Then they consider various families of graphs. For the complete graphs K_{n} the authors show that the weak and strong competitive ratios are H_{n} the n -th harmonic number, which is achieved by the natural greedy approach. They also show that this approach is almost optimal for complete k -partite graphs K_{n_{1},\ldots,n_{k}} . If the graph is a tree with diameter at most \Delta they provide an (1+\Delta/2) -competitive algorithm. In the final part of their work, the authors give results for the remaining graphs with four vertices. For the path with four vertices they claim that both the weak and strong competitive ratios are at least 2 and show an upper bound of 5/2 on both. For the graph K_{3}+e which you get by connecting an additional vertex to one vertex of K_{3} , they claim a lower bound of 13/6 for the weak competitive ratio and an upper bound of 5/2 for the strong competitive ratio. Finally, for K_{4}-e , the graph you get by deleting an edge from K_{4} , they claim that the weak competitive ratio is exactly 2 and show that the strong competitive ratio is below 5/2. Höhne and van Stee focus on graphs that are paths [ 11 ] . They close the gap for the path with four vertices by providing a 9/4 -competitive algorithm and a matching lower bound. For the path with 5 vertices they show that the competitive ratio is between 16/7 and 5/2 . For the general paths with at least 6 vertices they provide a lower bound of 12/5 and an upper bound linear in the number of vertices of n/2+1/4. They also introduce a new model called the flow model as described above. In this model the workload arrives at a constant rate over time in intervals instead of a block arriving at a specific point in time. So the workload function for the machines is continuous in time. This is a cleaner model which avoids the feature of the original model that the competitive ratio is usually achieved on the very last job that arrives, which then often increases the competitive ratio maintained so far by 1. Nevertheless, it is not the case that the competitive ratios for the two

Read the complete text