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.
C.A.J. Hurkens, A. Lodi, S. Martello, M. Monaci, G.J. Woeginger (2012). Complexity and approximation of an area packing problem. OPTIMIZATION LETTERS, 6, 1-9 [10.1007/s11590-010-0246-2].
Complexity and approximation of an area packing problem
LODI, ANDREA;MARTELLO, SILVANO;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:
Eventuali allegati, non sono esposti
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
