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 / C.A.J. Hurkens; A. Lodi; S. Martello; M. Monaci; G.J. Woeginger. - In: OPTIMIZATION LETTERS. - ISSN 1862-4472. - STAMPA. - 6:(2012), pp. 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.
