Covering problems

In combinatorics and computer science, covering problems are computational problems that ask whether a certain combinatorial structure 'covers' another, or how large the structure has to be to do that. Covering problems are minimization problems and usually linear programs, whose dual problems are called packing problems.

The most prominent examples of 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.

Covering/packing-problem pairs

|  Covering problems|  Packing problems

|

Minimum set cover|  Maximum set packing
Minimum vertex cover|  Maximum matching
Minimum edge cover|  Maximum independent set

* v
* t
* e

## Contents

* 1 General LP formulation
* 2 Other uses
* 3 See also
* 4 Notes
* 5 References
* 6 External links

## General 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] More precisely, consider the following general integer linear program:

minimize  | ∑i=1ncixi

|

subject to  | ∑i=1naijxi≥bj for j=1,…,m
| xi≥0 for i=1,…,n.

Such an integer linear program is called covering problem if aij,bj,ci≥0 for all i=1,…,n and j=1,…,m.

Intuition: Assume having n types of object and each object of type i has an associated cost of ci. The number xi indicates how many objects of type i we buy. If the constraints A𝐱≥𝐛 are satisfied, it is said that 𝐱 is a covering (the structures that are covered depend on the combinatorial context). Finally, an optimal solution to the above integer linear program is a covering of minimal cost.

## 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.

## See also

* The biclique edge cover problem asks for covering all edges of a given graph with (as few as possible) complete bipartite subgraphs.
* Disk covering problem, the problem of covering a unit circle with smaller circles
* Polygon covering, the problem of covering a complex polygon with simpler polygons such as squares or rectangles.
* The non-rectangle problem. The problem of covering a rectangular area without sub-rectangles. [2]

## Notes

1. ↑ (Vazirani 2001)
2. ↑ Martinez, Rebecca (1 March 2014). "March Puzzle". Triad Mensa 8 (3): 2. http://www.triad.us.mensa.org/pdfs2010/Mar14TM.pdf. Retrieved 20 April 2017.

## References

* Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. ISBN 3-540-65367-8.

## External links

* Erich's Packing Center contains some illustrations of geometric covering problems.

0.00

(0 votes)

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Covering_problems&oldid=174985"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template