An approximation result for a periodic allocation problem (Q5946816)

The paper introduces a periodic allocation problem which is a generalization of the dynamic storage allocation problem [see, e.g., \textit{E. G. Coffman}, SIAM Rev. 25, 311-325 (1983; Zbl 0521.68027)] to the case in which the arrival and departure time of each item is periodically repeated. This NP-hard problem can be regarded as an interval coloring problem on weighted circular arc graphs. The main result says that there exists an acyclic orientation of a Helly proper circular arc graph \(G\) in which each path of the orientation is contained in at most two maximal cliques of \(G\). This gives a 2-approximation algorithm for a class of periodic allocation problems.