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.
Membrane Algorithm, Min Storage, P systems
English
Membrane Computing: 7th International Workshop
2006
Membrane Computing: 7th International Workshop, WMC 7, Revised Selected and Invited Papers
978-3-540-69088-7
2006
4361
443
462
none
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].
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/10281/13141
Citazioni
  • Scopus 36
  • ???jsp.display-item.citation.isi??? 31
Social impact