In this paper we study a periodic allocation problem which is a generalization of the dynamic storage allocation problem to the case in which the arrival and departure time of each item is periodically repeated. These problems are equivalent to the interval coloring problem on weighted graphs in which each feasible solution corresponds to an acyclic orientation, and the solution value is equal to the length of the longest weighted path of the oriented graph. Optimal solutions correspond to acyclic orientations having the length of longest weighted path as small as possible. We prove that for the interval coloring problem on a class of circular arc graphs, and hence for a periodic allocation problem, there exists an approximation algorithm that 4nds a feasible solution whose value is at most two times the optimal.

Confessore, G., Dell'Olmo, P., Giordani, S. (2001). An Approximation Result for a Periodic Allocation Problem. DISCRETE APPLIED MATHEMATICS, 112, 53-72 [10.1016/S0166-218X(00)00309-7].

An Approximation Result for a Periodic Allocation Problem

GIORDANI, STEFANO
2001-01-01

Abstract

In this paper we study a periodic allocation problem which is a generalization of the dynamic storage allocation problem to the case in which the arrival and departure time of each item is periodically repeated. These problems are equivalent to the interval coloring problem on weighted graphs in which each feasible solution corresponds to an acyclic orientation, and the solution value is equal to the length of the longest weighted path of the oriented graph. Optimal solutions correspond to acyclic orientations having the length of longest weighted path as small as possible. We prove that for the interval coloring problem on a class of circular arc graphs, and hence for a periodic allocation problem, there exists an approximation algorithm that 4nds a feasible solution whose value is at most two times the optimal.
2001
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore MAT/09 - RICERCA OPERATIVA
English
Con Impact Factor ISI
Periodic allocation; Multiprocessor task scheduling; Interval coloring; Circular arc graphs; Helly property; Clique partition; Approximation result.
http://dx.doi.org/10.1016/S0166-218X(00)00309-7
Confessore, G., Dell'Olmo, P., Giordani, S. (2001). An Approximation Result for a Periodic Allocation Problem. DISCRETE APPLIED MATHEMATICS, 112, 53-72 [10.1016/S0166-218X(00)00309-7].
Confessore, G; Dell'Olmo, P; Giordani, S
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/52086
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact