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 al- gorithm 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) coecien t 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. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1007/11963516_28 | Workshop on Membrane Computing |
Keywords | Field | DocType |
hard optimization problem,approximate solution,min storage problem,traditional approximation technique,min storage,membrane algorithm,polynomial time heuristics,polynomial time membrane algorithm,input value,polynomial time,optimization problem | Storage Problem,Positive element,Algorithm,Travelling salesman problem,Heuristics,Time complexity,Optimization problem,Mathematics,Computation | Conference |
Volume | ISSN | ISBN |
4361 | 0302-9743 | 3-540-69088-3 |
Citations | PageRank | References |
15 | 1.08 | 7 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Alberto Leporati | 1 | 494 | 51.97 |
Dario Pagani | 2 | 15 | 1.08 |