Covering problems: Difference between revisions

Revision as of 16:28, 11 March 2009

Latest revision as of 09:34, 1 September 2025

(46 intermediate revisions by 27 users not shown)

Line 1:

{{Short description|Type of computational 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 [[Optimization (mathematics)|minimization problem]]s and usually [[integer linear programs]], whose [[dual problem]]s are called [[packing problems]].

Covering problems are usually [[dual problem|dual]] to [[packing problem]]s.

Important covering problems are the [[Set cover problem]], which is equivalent to the [[Hitting set|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|set packing problem]].

ImportantThe most prominent examples of covering problems are the [[Setset cover problem]], which is equivalent to the [[Hitting set|Hittinghitting Setset Problemproblem]], and its special cases, the [[Vertexvertex cover problem]] and the [[Edgeedge cover problem]]. The set cover problem is dual to the [[set packing|set packing problem]].

Covering problems allow the covering primitives to overlap; the process of covering something with non-overlapping primitives is called [[decomposition (disambiguation)|decomposition]].

==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<ref>{{harvtxt|Vazirani|2001}}</ref>. Let <math>\mathbf{b},\mathbf{c}</math> be vectors and <math>A</math> be a matrix, all with no negative entries. Then one can see the following [[integer linear program]] as the most general covering problem:

{{Covering-Packing_Problem_Pairs}}

: minimize <math>\mathbf{c}^T \mathbf{x}</math>

==General linear programming formulation==

: subject to <math>A \mathbf{x}\geq \mathbf{b}, \mathbf{x}\in\{0,1\}</math>

In the context of [[linear programming]], one can think of any minimization linear program as a covering problem if the coefficients in the constraint [[matrix (mathematics)|matrix]], the objective function, and right-hand side are nonnegative.<ref>{{Cite book | last=Vazirani | first=Vijay V. | author-link=Vijay Vazirani | title=Approximation Algorithms | year=2001 | publisher=Springer-Verlag | isbn=3-540-65367-8 }}{{rp|112}}

</ref> More precisely, consider the following general [[integer linear program]]:

{|

| minimize

| <math>\sum_{i=1}^n c_i x_i</math>

|-

| subject to

| <math> \sum_{i=1}^n a_{ji} x_i \geq b_j \text{ for }j=1,\dots,m</math>

|-

|

| <math>x_i \in \left\{0, 1, 2, \ldots\right\}\text{ for }i=1,\dots,n</math>.

|}

Such an integer linear program is called a '''covering problem''' if <math>a_{ji}, b_j, c_i \geq 0</math> for all <math>i=1,\dots,n</math> and <math>j=1,\dots,m</math>.

The'''Intuition:''' Assume having <math>in</math>th entrytypes of theobject and each object of vectortype <math>\mathbf{x}i</math> tellshas us,an whetherassociated wecost takeof object<math>c_i</math>. The number <math>ix_i</math> intoindicates ourhow covermany orobjects of type <math>i</math> we notbuy. TheIf the constraints <math>A\mathbf{x}\geq \mathbf{b}</math> tellare ussatisfied, what it meansis forsaid that ''<math>\mathbf{x}</math> tois covera allcovering'' object(the structures that are covered depend on the combinatorial context). Finally, thean costoptimal functionsolution <math>\mathbf{c}</math>to definesthe whatabove weinteger considerlinear toprogram beis a 'cheap'covering coverof minimal cost.

==Kinds of covering problems==

==Other uses==

There are various kinds of covering problems in [[graph theory]], [[computational geometry]] and more; see [[:Category:Covering problems]]. Other stochastic related versions of the problem can be found.<ref>{{cite web|author = Douek-Pinkovich, Y., Ben-Gal, I., & Raviv, T. (2022)|title = The Stochastic Test Collection Problem: Models, Exact and Heuristic Solution Approaches |url = http://www.eng.tau.ac.il/~bengal/STCP.pdf|publisher = European Journal of Operational Research, 299 (2022), 945–959} }}</ref>

For [[Petri net]]s, 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.

[[File:Covering problem of Rado.gif|thumb|500px|The [[covering problem of Rado]], where a series of squares with parallel edges needs to cover an area of 1. For any set meeting these conditions, a subset of these squares is selected (indicated by the red coloring) in which no two squares overlap, and the total area is maximized. The goal is to make an arrangement of squares so that the total area of the optimal subset is ''minimized''. The examples each have maximal areas of 1/4, but there are some which have slightly lower.

==Notes==

<ref>{{citation

{{reflist}}

| last = Ajtai | first = Miklós | author-link = Miklós Ajtai

| journal = Bulletin de l'Académie Polonaise des Sciences, Série des Sciences Mathématiques, Astronomiques et Physiques

| mr = 319053

| pages = 61–63

| title = The solution of a problem of T. Radó

| volume = 21

| year = 1973}}</ref>

<ref>{{citation

| last1 = Bereg | first1 = Sergey

| last2 = Dumitrescu | first2 = Adrian

| last3 = Jiang | first3 = Minghui

| doi = 10.1007/s00453-009-9298-z

| issue = 3

| journal = Algorithmica

| mr = 2609053

| pages = 538–561

| title = On covering problems of Rado

| volume = 57

| year = 2010}}; preliminary announcement in [[SWAT and WADS conferences|SWAT 2008]], {{doi|10.1007/978-3-540-69903-3_27}}</ref>]]

[[File:DiscCoveringExample.svg|thumb|200px|The [[disk covering problem]], which asks what the smallest real number <math>r(n)</math> is such that <math>n</math> disks of radius <math>r(n)</math> can be arranged in such a way as to cover the unit disk.]]

=== Covering in Petri nets ===

For [[Petri net]]s, 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.

=== Rainbow covering{{Anchor|rainbow}} ===

In some covering problems, the covering should satisfy some additional requirements. In particular, in the '''rainbow covering''' problem, each of the original objects has a "color", and it is required that the covering contains exactly one (or at most one) object of each color. Rainbow covering was studied e.g. for covering points by [[interval (mathematics)|intervals]]:<ref>{{Cite journal|last1=Arkin|first1=Esther M.|last2=Banik|first2=Aritra|last3=Carmi|first3=Paz|last4=Citovsky|first4=Gui|last5=Katz|first5=Matthew J.|last6=Mitchell|first6=Joseph S. B.|last7=Simakov|first7=Marina|date=2018-12-11|title=Selecting and covering colored points|journal=Discrete Applied Mathematics|language=en|volume=250|pages=75–86|doi=10.1016/j.dam.2018.05.011|issn=0166-218X|doi-access=free}}</ref>

* There is a set ''J'' of ''n'' colored intervals on the [[real line]], and a set ''P'' of points on the real line.

* A [[subset]] ''Q'' of ''J'' is called a ''rainbow set'' if it contains at most a single interval of each color.

* A set of intervals ''J'' is called a ''covering'' of ''P'' if each point in ''P'' is contained in at least one interval of ''Q''.

* The ''Rainbow covering problem'' is the problem of finding a rainbow set ''Q'' that is a covering of ''P''.

The problem is [[NP-hardness|NP-hard]] (by reduction from [[linear SAT]]).

=== Conflict-free covering ===

A more general notion is '''conflict-free covering'''.<ref>{{Cite journal|last1=Banik|first1=Aritra|last2=Sahlot|first2=Vibha|last3=Saurabh|first3=Saket|date=2020-08-01|title=Approximation algorithms for geometric conflict free covering problems|url=http://www.sciencedirect.com/science/article/pii/S0925772119301324|journal=Computational Geometry|language=en|volume=89|pages=101591|doi=10.1016/j.comgeo.2019.101591|s2cid=209959954 |issn=0925-7721|url-access=subscription}}</ref> In this problem:

* There is a set ''O'' of ''m'' objects, and a conflict-graph ''G_O'' on ''O''.

* A subset ''Q'' of ''O'' is called ''conflict-free'' if it is an [[Independent set (graph theory)|independent set]] in ''G_O'', that is, no two objects in ''Q'' are connected by an edge in ''G_O''.

* A rainbow set is a conflict-free set in the special case in which ''G_O'' is made of disjoint cliques, where each clique represents a color.

''Conflict-free set cover'' is the problem of finding a conflict-free subset of ''O'' that is a covering of ''P''. Banik, Panolan, Raman, Sahlot and Saurabh<ref>{{Cite journal|last1=Banik|first1=Aritra|last2=Panolan|first2=Fahad|last3=Raman|first3=Venkatesh|last4=Sahlot|first4=Vibha|last5=Saurabh|first5=Saket|date=2020-01-01|title=Parameterized Complexity of Geometric Covering Problems Having Conflicts|url=https://doi.org/10.1007/s00453-019-00600-w|journal=Algorithmica|language=en|volume=82|issue=1|pages=1–19|doi=10.1007/s00453-019-00600-w|s2cid=254027914 |issn=1432-0541|url-access=subscription}}</ref> [[mathematical proof|prove]] the following for the special case in which the conflict-graph has bounded [[arboricity]]:

* If the geometric cover problem is [[Fixed-parameter algorithm|fixed-parameter]] tractable (FPT), then the conflict-free geometric cover problem is FPT.

* If the geometric cover problem admits an r-approximation algorithm, then the conflict-free geometric cover problem admits a similar approximation algorithm in FPT time.

==References==

{{reflist}}

* {{Cite book | last=V. Vazirani | first=Vijay | authorlink=Vijay Vazirani | coauthors= | title=Approximation Algorithms | date=2001 | publisher=Springer-Verlag | ___location= | isbn=3-540-65367-8 | pages=}}

[[Category:CombinatoricsCovering problems|*]]

[[Category:Theoretical computer science]]

[[Category:Mathematical problems]]