Complexity and approximation of an area packing problem

C.A.J. Hurkens, A. Lodi, S. Martello, M. Monaci, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
3 Downloads (Pure)

Abstract

Motivated by an application in mobile telecommunication systems, we investigate a packing problem in which items are specified in terms of area constraints. We establish strong -hardness of this problem, provide a linear time 3-approximation algorithm, and discuss the combinatorics of a special case.
Original languageEnglish
Pages (from-to)1-9
JournalOptimization Letters
Volume6
Issue number1
DOIs
Publication statusPublished - 2012

Fingerprint Dive into the research topics of 'Complexity and approximation of an area packing problem'. Together they form a unique fingerprint.

  • Cite this