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 \({{\mathcal {NP}}}\)-hardness of this problem, provide a linear time 3-approximation algorithm, and discuss the combinatorics of a special case. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/s11590-010-0246-2 | Optimization Letters |
Keywords | Field | DocType |
Area packing, Complexity, Approximation, Worst case analysis | Discrete mathematics,Combinatorics,Mathematical optimization,Packing problems,Set packing,Time complexity,Mobile telecommunication systems,Bin packing problem,Mathematics,Special case | Journal |
Volume | Issue | ISSN |
6 | 1 | 1862-4480 |
Citations | PageRank | References |
6 | 0.45 | 3 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Cor A. J. Hurkens | 1 | 430 | 30.75 |
Andrea Lodi | 2 | 2198 | 152.51 |
Silvano Martello | 3 | 2362 | 218.73 |
Michele Monaci | 4 | 1049 | 60.78 |
Gerhard Woeginger | 5 | 4176 | 384.37 |