An approximation result for a periodic allocation problem

DOI10.1016/S0166-218X(00)00309-7MaRDI QIDQ5946816zbMATH OpenOpenAlexWikidataFDO

Authors Giuseppe Confessore, Paolo Dell'Olmo, Stefano Giordani

Publication date 30 July 2002

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(00)00309-7

zbMATH Keywords

approximation algorithmcircular arc graphclique partitiongraphHelly propertyinterval coloringmultiprocessor task schedulingperiodic allocation

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Applications of graph theory (05C90) Deterministic scheduling theory in operations research (90B35) Programming involving graphs or networks (90C35)

Review text

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.

Recommendations

• A polynomial time approximation algorithm for dynamic storage allocation
• Periodic assignment and graph colouring
• An approximation algorithm for circular arc colouring
• On \(k\)-coloring of weighted circular-arc graphs
• Perfect circular arc coloring

Cites work

• A Characterization of Comparability Graphs and of Interval Graphs
• A polynomial time approximation algorithm for dynamic storage allocation
• Algorithms on circular-arc graphs
• An approximation result for a duo-processor task scheduling problem
• An Introduction to Combinatorial Models of Dynamic Storage Allocation
• Approximation algorithms for dynamic storage allocation
• Comparability graph augmentation for some multiprocessor scheduling problems
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1304159 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• On chordal proper circular arc graphs
• On the compatibility between a graph and a simple order
• Structure theorems for some circular-arc graphs
• The Complexity of Coloring Circular Arcs and Chords
• The Linearity of First-Fit Coloring of Interval Graphs

Cited in

(5)

• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Periodic assignment and graph colouring
• An approximation result for the interval coloring problem on claw-free chordal graphs
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• On some subclasses of oriented catch digraphs

This page was built for publication: An approximation result for a periodic allocation problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5946816)