Motivated by an application in mobile telecommunication systems, we investigate a packing problem in which items are specified in terms of area con- straints. We establish strong NP-hardness of this problem, provide a linear time 3-approximation algorithm, and discuss the combinatorics of a special case.
Complexity and approximation of an area packing problem
MONACI, MICHELE;
2012
Abstract
Motivated by an application in mobile telecommunication systems, we investigate a packing problem in which items are specified in terms of area con- straints. We establish strong NP-hardness of this problem, provide a linear time 3-approximation algorithm, and discuss the combinatorics of a special case.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
