NP-hardness conjecture for limited-capacity covering and packing
NP-hardness conjecture for limited-capacity covering and packing
Let be a convex body and let be an integer. The decision problem --COVER asks whether a given point set can be covered by homothets of with each homothet containing at most points; similarly, --PACK asks whether a prescribed number of homothets of can be selected subject to each homothet containing at most points.
NP-hardness conjecture. --COVER is NP-hard for every convex body and every integer . Similarly, --PACK is NP-hard for every convex body and every integer .
The conjecture extends the paper's NP-hardness results beyond the particular cases handled by its reduction to -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.