patternMinor
Can all packing/covering problems be rephrased as set packing/covering problems?
Viewed 0 times
canallpackingrephrasedcoveringproblemsset
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#6362, answer score: 2
Revisions (0)
No revisions yet.