Content deleted Content added
Erel Segal (talk | contribs) |
m Open access bot: url-access=subscription updated in citation with #oabot. |
||
| (4 intermediate revisions by 3 users not shown) | |||
Line 4:
The most prominent examples of 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]].
Covering
{{Covering-Packing_Problem_Pairs}}
Line 26:
==Kinds of covering problems==
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>
[[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.
<ref>{{citation
| 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 ===
Line 41 ⟶ 64:
=== 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<sub>O</sub>'' on ''O''.
Line 47 ⟶ 70:
* A rainbow set is a conflict-free set in the special case in which ''G<sub>O</sub>'' 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.
| |||