6
$\begingroup$

Can all packing problems be rephrased as set packing problems?

Can all covering problems be rephrased as set covering problems?

In other words, I was wondering if set packing/covering problems are the most general forms of packing/covering problems?

$\endgroup$
  • 3
    $\begingroup$ Packing/covering problems are larger classes of problems, because the "standard" set packing/covering problems only deal with finite sets (see their definitions). Furthermore you can formulate packing/covering problems using uncomputable stuff; for example: "How many circles of ray $K(x)$ are needed to cover a $x \times x$ square; where $K(x)$ is the Kolmogorov complexity of the binary representation of $x$?" $\endgroup$ – Vor Oct 29 '12 at 0:01
  • $\begingroup$ I edited out the fourth, less related question. If you are still interested, please ask it separately. $\endgroup$ – Raphael Feb 23 '15 at 11:36
2
$\begingroup$

If we restrict ourselves to problems in NP, then yes. There are NP-complete problems of either category, so (many-one poly-time) reductions exist; we can view these as "rephrasing".

Since integer programming is also NP-complete, these same is true for that one.

Problems outside of NP do not reduce to integer programming, but I am sure that any (meaningful) complexity class contains examples of both covering and packing problems.

It's not the "type" of a problem that determines its hardness. There are satisfiability problems all the way from linear complexity to undecidability, to name just one example.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.