Editing Set cover problem (section)

== References ==

* {{Citation | last1=Alon | first1=Noga | author1-link=Noga Alon | last2=Moshkovitz | first2=Dana|author2-link= Dana Moshkovitz | last3=Safra | first3=Shmuel | author3-link=Shmuel Safra | title=Algorithmic construction of sets for k-restrictions | year=2006 | journal=ACM Trans. Algorithms | issn=1549-6325 | volume=2 | issue=2 | pages=153–177 | doi=10.1145/1150334.1150336| citeseerx=10.1.1.138.8682 | s2cid=11922650 }}.
* {{Citation
 | last1=Cormen     | first1=Thomas H.   | author-link=Thomas H. Cormen
 | last2=Leiserson | first2=Charles E. | author-link2=Charles E. Leiserson
 | last3=Rivest    | first3=Ronald L.  | author-link3=Ronald L. Rivest
 | last4=Stein     | first4=Clifford   | author-link4=Clifford Stein
 | title=Introduction to Algorithms | year=2001 | publisher=MIT Press and McGraw-Hill | location=Cambridge, Mass.
 | isbn=978-0-262-03293-3 | pages=1033–1038}}
* {{Citation | last1=Feige | first1=Uriel | author1-link=Uriel Feige | title=A threshold of ln n for approximating set cover | year=1998 | journal=[[Journal of the ACM]] | issn=0004-5411 | volume=45 | issue=4 | pages=634–652 | doi=10.1145/285055.285059| citeseerx=10.1.1.70.5014 | s2cid=52827488 }}.
* {{Citation
 | last1=Karpinski | first1=Marek | last2=Zelikovsky|first2=Alexander
 | year=1998
 | contribution=Approximating dense cases of covering problems
 | title=Proceedings of the DIMACS Workshop on Network Design: Connectivity and Facilities Location
 | volume=40
 | pages=169–178
 | publisher=American Mathematical Society | url=https://books.google.com/books?id=IMmuF0RZk1MC&q=karpinski+zelikovsky+cover+dense&pg=PA169
| isbn=9780821870846 }}
* {{Citation | last1=Lund | first1=Carsten | author1-link=Carsten Lund | last2=Yannakakis | first2=Mihalis | author2-link=Mihalis Yannakakis | title=On the hardness of approximating minimization problems | year=1994 | journal=[[Journal of the ACM]] | issn=0004-5411 | volume=41 | issue=5 | pages=960–981 | doi=10.1145/185675.306789| s2cid=9021065 | doi-access=free }}.
* {{Citation | last1=Raz | first1=Ran | author1-link=Ran Raz | last2=Safra | first2=Shmuel | author2-link=Shmuel Safra | title=STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing | publisher=ACM | isbn=978-0-89791-888-6 | year=1997 | chapter=A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP | pages=475–484}}.
* {{Citation | last1=Dinur | first1=Irit | author1-link=Irit Dinur | last2=Steurer | first2=David | title=STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing | publisher=ACM | year=2013 | chapter=Analytical approach to parallel repetition | pages=624–633}}.
* {{Citation| last = Vazirani | first = Vijay V.
 | author-link = Vijay Vazirani
 | title = Approximation Algorithms
 | year = 2001
 | publisher = Springer-Verlag
 | isbn = 978-3-540-65367-7
 | url = https://www.ics.uci.edu/~vazirani/book.pdf
 }}
* {{Citation| last1 = Korte | first1 = Bernhard | authorlink1=Bernhard Korte
 | last2 = Vygen | first2 = Jens
 | title = Combinatorial Optimization: Theory and Algorithms
 | year = 2012
 | isbn = 978-3-642-24487-2
 | edition = 5
 | publisher = Springer
 }}
* {{Citation| last1 = Cardoso | first1 = Nuno | last2 = Abreu | first2 = Rui | contribution = An Efficient Distributed Algorithm for Computing Minimal Hitting Sets | year = 2014 | title=Proceedings of the 25th International Workshop on Principles of Diagnosis |location=Graz, Austria | contribution-url = http://dx-2014.ist.tugraz.at/papers/DX14_Mon_PM_S1_paper1.pdf | doi=10.5281/zenodo.10037 }}
* {{Citation
 | last1=Dinur     | first1=Irit       | author-link=Irit Dinur
 | last2=Guruswami | first2=Venkatesan | author-link2=Venkatesan Guruswami
 | last3=Khot      | first3=Subhash    | author-link3=Subhash Khot
 | last4=Regev     | first4=Oded       | author-link4=Oded Regev (computer scientist)
 | title=A new multilayered PCP and the hardness of hypergraph vertex cover 
 | year=2003 
 | isbn=1581136749 | publisher=Association for Computing Machinery
 | pages=595–601
 | doi=10.1145/780542.780629 | url = https://doi.org/10.1145/780542.780629
}}
* {{Citation
 | last1=Khot      | first1=Subhash    | author-link=Subhash Khot
 | last2=Regev     | first2=Oded       | author-link2=Oded Regev (computer scientist)
 | title=Vertex cover might be hard to approximate to within 2−<math>\epsilon</math> 
 | year=2008
 | publisher=Journal of Computer and System Sciences
 | url = https://doi.org/10.1016/j.jcss.2007.06.019
 | pages=335–349
| doi=10.1016/j.jcss.2007.06.019 }}
* {{Citation
 | last1=Trevisan   | first1=Luca       | title=Proceedings of the thirty-third annual ACM symposium on Theory of computing | author-link=Luca Trevisan
 | chapter=Non-approximability results for optimization problems on bounded degree instances 
 | year=2001
 | publisher=Association for Computing Machinery
 | chapter-url = https://doi.org/10.1145/380752.380839
 | pages=453–461
| doi=10.1145/380752.380839 | isbn=1-58113-349-9 }}