Min Storage is an NP–hard optimization problem that arises in a natural way when one considers computations in which the amount of energy provided with the input values is preserved during the computation. In this paper we propose a polynomial time membrane algorithm that computes approximate solutions to the instances of Min Storage, and we study its behavior on (almost) uniformly randomly chosen instances. Moreover, we compare the (estimated) coefficient of approximation of this algorithm with the ones obtained from several other polynomial time heuristics. The result of this comparison indicates the superiority of the membrane algorithm with respect to many other traditional approximation techniques.
Leporati, A., Pagani, D. (2006). A membrane algorithm for the min storage problem. In Membrane Computing: 7th International Workshop, WMC 7, Revised Selected and Invited Papers (pp.443-462). Springer [10.1007/11963516_28].
A membrane algorithm for the min storage problem
LEPORATI, ALBERTO OTTAVIO;
2006
Abstract
Min Storage is an NP–hard optimization problem that arises in a natural way when one considers computations in which the amount of energy provided with the input values is preserved during the computation. In this paper we propose a polynomial time membrane algorithm that computes approximate solutions to the instances of Min Storage, and we study its behavior on (almost) uniformly randomly chosen instances. Moreover, we compare the (estimated) coefficient of approximation of this algorithm with the ones obtained from several other polynomial time heuristics. The result of this comparison indicates the superiority of the membrane algorithm with respect to many other traditional approximation techniques.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.