Covering problem

Covering problem

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 dualities
Covering problems Packing problems
Minimum set cover Maximum set packing
Minimum vertex cover Maximum matching
Minimum edge cover Maximum independent set

Contents

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, let us consider the following general integer linear program:

minimize \sum_{i=1}^n c_i x_i
subject to  \sum_{i=1}^n a_{ij} x_i \geq b_j \text{ for }j=1,\dots,m
x_i \geq 0\text{ for }i=1,\dots,n.

Such an integer linear program is called covering problem if a_{ij}, b_j, c_i \geq 0 for all i=1,\dots,n and j=1,\dots,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\mathbf{x}\geq \mathbf{b} are satisfied, it is said that \mathbf{x} 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

Notes

  1. ^ Vazirani (2001, p. 112)

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Covering problem of Rado — The covering problem of Rado is an unsolved problem in geometry concerning covering planar sets by squares. It was formulated in 1928 by Tibor Radó and has been generalized to more general shapes and higher dimensions by Richard Rado. Formulation …   Wikipedia

  • Disk covering problem — The disk covering problem was proposed by C. T. Zahn in 1962. Given an integer n, the problem asks for the smallest real number r(n) such that n disks of radius r(n) can be arranged in such a way as to cover the unit disk. The best solutions to… …   Wikipedia

  • Covering code — In coding theory, a covering code is an object satisfying a certain mathematical property: A code of length n over Q is an R covering code if for every word of Qn there is a codeword such that their Hamming distance is . Contents 1 Definition 2… …   Wikipedia

  • Covering: The Hidden Assault on Our Civil Rights —   …   Wikipedia

  • Covering (graph theory) — In the mathematical discipline of graph theory, a covering (or cover) of a graph is a set of vertices (or edges) such that each edge (vertex) of the graph touches (is incident with) at least one element of the set.It is of mathematical interest… …   Wikipedia

  • Covering system — In mathematics, a covering system (also called a complete residue system) is a collection of finitely many residue classes whose union covers all the integers. Unsolved problems in mathematics For any arbitrarily large natural number N does there …   Wikipedia

  • Covering of the Senne — Construction of the covering and tunnels. The covering of the Senne (French: voûtement de la Senne, Dutch: overwelving van de Zenne) was one of the defining events in the history of Brussels. The Senne/Zenne (French/Dutch) was historically the m …   Wikipedia

  • Covering of the eyes — The phrase covering of eyes is found in Genesis 20:16. It is translated literally in Young s Literal Translation. The King James Version inserts the definite article the , absent in the original text. Almost all other versions treat it as a… …   Wikipedia

  • Problem der exakten Überdeckung — Das Problem der exakten Überdeckung (englisch Exact Cover) ist ein Entscheidungsproblem der Kombinatorik. Es gehört zu den 21 klassischen NP vollständigen Problemen, von denen Richard M. Karp 1972 gezeigt hat, dass sie NP vollständig sind.… …   Deutsch Wikipedia

  • Set cover problem — The set covering problem is a classical question in computer science and complexity theory. As input you are given several sets. They may have some elements in common. You must select a minimum number of these sets so that the sets you have… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”