论文标题
关于凸多边形的二维背包问题
On the Two-Dimensional Knapsack Problem for Convex Polygons
论文作者
论文摘要
我们研究了凸多边形的二维几何背包问题。鉴于一组加权凸多边形和方形背包，目标是选择给定多边形的最有利可图的子集，该子集适用于主背包。我们允许通过任意角度旋转多边形。我们提供一个准多项式时间$ o（1）$ - 常规情况的近似算法，如果所有输入多边形都是三角形的，则均为多项式时间$ o（1）$ - 近似算法，都假设多项式限制了积分输入数据。另外，我们给出了一种准多项式时间算法，该算法计算资源增强下的最佳权重解决方案，即，我们允许将背包的大小增加$ 1+δ$ $δ> 0 $的$ 1+δ$，但将自己与原始Knapsack的最佳解决方案相比。据我们所知，这些是二维几何背包的第一个结果，其中输入对象比轴平行的矩形或圆圈更一般，并且可以通过任意角度旋转输入多边形。
We study the two-dimensional geometric knapsack problem for convex polygons. Given a set of weighted convex polygons and a square knapsack, the goal is to select the most profitable subset of the given polygons that fits non-overlappingly into the knapsack. We allow to rotate the polygons by arbitrary angles. We present a quasi-polynomial time $O(1)$-approximation algorithm for the general case and a polynomial time $O(1)$-approximation algorithm if all input polygons are triangles, both assuming polynomially bounded integral input data. Also, we give a quasi-polynomial time algorithm that computes a solution of optimal weight under resource augmentation, i.e., we allow to increase the size of the knapsack by a factor of $1+δ$ for some $δ>0$ but compare ourselves with the optimal solution for the original knapsack. To the best of our knowledge, these are the first results for two-dimensional geometric knapsack in which the input objects are more general than axis-parallel rectangles or circles and in which the input polygons can be rotated by arbitrary angles.
