NP-hardness conjecture for limited-capacity covering and packing

At least 3 years old · documented by

Let CC be a convex body and let k≥3k\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 k≥3k\geq 3. Similarly, CC-kk-PACK is NP-hard for every convex body CC and every integer k≥2k\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.

References

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.