Covering problems

In combinatorics and computer science, covering problems are computational problems that ask whether a certain structure 'covers' another, or how large the structure has to be to do that. Covering problems are usually dual to packing problems. Important covering problems are the Set cover problem, which is equivalent to the Hitting Set Problem, and its special cases, the Vertex cover problem and the Edge cover problem. The set cover problem is dual to the set packing problem.

LP Formulation

In the context of linear programming, one can think of any linear program as a covering problem if the coefficients in the constraint matrix, the objective function, and right-hand side are nonnegative^[1]. Let ${\displaystyle \mathbf {b} ,\mathbf {c} }$  be vectors and ${\displaystyle A}$  be a matrix, all with no negative entries. Then one can see the following integer linear program as the most general covering problem:

minimize ${\displaystyle \mathbf {c} ^{T}\mathbf {x} }$ 

subject to ${\displaystyle A\mathbf {x} \geq \mathbf {b} ,\mathbf {x} \in \{0,1\}}$ 

The ${\displaystyle i}$ th entry of the vector ${\displaystyle \mathbf {x} }$  tells us, whether we take object ${\displaystyle i}$  into our cover or not. The constraints ${\displaystyle A\mathbf {x} \geq \mathbf {b} }$  tell us, what it means for ${\displaystyle \mathbf {x} }$  to cover all object. Finally the cost function ${\displaystyle \mathbf {c} }$  defines what we consider to be a 'cheap' cover.

Other uses

For Petri nets, for example, the covering problem is defined as the question if for a given marking, there exists a run of the net, such that some larger (or equal) marking can be reached. Larger means here that all components are at least as large as the ones of the given marking and at least one is properly larger.

Notes

1. V. Vazirani (2001)

References

• V. Vazirani, Vijay (2001). Approximation Algorithms. Springer-Verlag. ISBN 3-540-65367-8. {{cite book}}: Cite has empty unknown parameter: |coauthors= (help)