NP-hardness conjecture for limited-capacity covering and packing

Let CC be a convex body and let k3k\geq 3 be an integer. The decision problem CC-kk-COVER asks whether a given point set can be covered by homothets of CC with each homothet containing at most kk points; similarly, CC-kk-PACK asks whether a prescribed number of homothets of CC can be selected subject to each homothet containing at most kk points.

NP-hardness conjecture. CC-kk-COVER is NP-hard for every convex body CC and every integer k3k\geq 3. Similarly, CC-kk-PACK is NP-hard for every convex body CC and every integer k2k\geq 2.

The conjecture extends the paper's NP-hardness results beyond the particular cases handled by its reduction to 33-SAT and by earlier work. Its status is not resolved in the supplied source context.

Sources & referencesView supporting material

Primary source

Oriol Solé Pi, “Covering and packing with homothets of limited capacity”, arXiv:2211.09328 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.