Complexity and approximation of an area packing problem

Complexity and approximation of an area packing problem

0.00 Avg rating0 Votes
Article ID: iaor2012320
Volume: 6
Issue: 1
Start Page Number: 1
End Page Number: 9
Publication Date: Jan 2012
Journal: Optimization Letters
Authors: , , , ,
Keywords: approximation, complexity, wireless access networks
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 𝒩𝒫 equ1 ‐hardness of this problem, provide a linear time 3‐approximation algorithm, and discuss the combinatorics of a special case.

Reviews

Required fields are marked *. Your email address will not be published.