Name
Abstract | ||
|---|---|---|
The two-dimensional box placement problem involves finding a position to place a rectangular box into a container given n rectangular boxes that have already been placed. It commonly arises as a subproblem in many algorithms for cutting stock and packing problems. We develop an asymptotically optimal approach for finding the bottom-leftmost feasible position, and modify it to find all normal feasible positions (which is also asymptotically optimal). Our approach relies on augmented versions of the segment tree data structure, and is simpler and more practicable than the best existing approach. Furthermore, it does not require that the placed boxes are interior-disjoint. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-21827-9_25 | IEA/AIE (2) |
Keywords | Field | DocType |
normal feasible position,augmented version,asymptotically optimal approach,rectangular box,asymptotically optimal,existing approach,optimal algorithm,two-dimensional box placement problem,bottom-leftmost feasible position,n rectangular box,segment tree data structure,combinatorial optimization | Data structure,Mathematical optimization,Packing problems,Computer science,Algorithm,Combinatorial optimization,Cuboid,Segment tree,Asymptotically optimal algorithm,Vlsi layout | Conference |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wenbin Zhu | 1 | 29 | 3.09 |
| Wee-chong Oon | 2 | 111 | 12.72 |
| Yujian Weng | 3 | 11 | 0.83 |
| Andrew Lim | 4 | 150 | 13.57 |