{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihv4xnohekinzianfzbczomwfvf7kk2jgtmmjdptso6fy7t4fnsme",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mhz222gtkln2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.23970v1",
  "publishedAt": "2026-03-26T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Debajyoti Kar",
    "Arindam Khan",
    "Andreas Wiese"
  ],
  "textContent": "**Authors:** Debajyoti Kar, Arindam Khan, Andreas Wiese\n\nWe study the two-dimensional (geometric) knapsack problem with rotations (2DKR), in which we are given a square knapsack and a set of rectangles with associated profits. The objective is to find a maximum profit subset of rectangles that can be packed without overlap in an axis-aligned manner, possibly by rotating some rectangles by $90^{\\circ}$. The best-known polynomial time algorithm for the problem has an approximation ratio of $3/2+ε$ for any constant $ε>0$, with an improvement to $4/3+ε$ in the cardinality case, due to G{á}lvez et al. (FOCS 2017, TALG 2021). Obtaining a PTAS for the problem, even in the cardinality case, has remained a major open question in the setting of multidimensional packing problems, as mentioned in the survey by Christensen et al. (Computer Science Review, 2017). In this paper, we present a PTAS for the cardinality case of 2DKR. In contrast to the setting without rotations, we show that there are $(1+ε)$-approximate solutions in which all items are packed greedily inside a constant number of rectangular {\\em containers}. Our result is based on a new resource contraction lemma, which might be of independent interest. In contrast, for the general weighted case, we prove that this simple type of packing is not sufficient to obtain a better approximation ratio than $1.5$. However, we break this structural barrier and design a $(1.497+ε)$-approximation algorithm for 2DKR in the weighted case. Our arguments also improve the best-known approximation ratio for the (weighted) case {\\em without rotations} to $13/7+ε\\approx 1.857+ε$. Finally, we establish a lower bound of $n^{Ω(1/ε)}$ on the running time of any $(1+ε)$-approximation algorithm for our problem with or without rotations -- even in the cardinality setting, assuming the $k$-\\textsc{Sum} Conjecture.",
  "title": "Approximation Schemes and Structural Barriers for the Two-Dimensional Knapsack Problem with Rotations"
}