{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:05Z","timestamp":1740109265265,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2017,8,22]],"date-time":"2017-08-22T00:00:00Z","timestamp":1503360000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,10]]},"DOI":"10.1007\/s00453-017-0357-6","type":"journal-article","created":{"date-parts":[[2017,8,22]],"date-time":"2017-08-22T14:50:38Z","timestamp":1503413438000},"page":"2874-2908","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Ordered Covering Problem"],"prefix":"10.1007","volume":"80","author":[{"given":"Uriel","family":"Feige","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7709-8486","authenticated-orcid":false,"given":"Yael","family":"Hitron","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,8,22]]},"reference":[{"key":"357_CR1","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"S Arora","year":"1997","unstructured":"Arora, S., Lund, C.: Hardness of Approximation. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, Boston (1997)"},{"issue":"2","key":"357_CR2","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1006\/jcss.1997.1472","volume":"54","author":"S Arora","year":"1997","unstructured":"Arora, S., Babai, L., Stern, J., Sweedyk, E.: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci. 54(2), 317\u2013331 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"357_CR3","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities: an $$\\mathit{O}(\\mathit{n}^{\\text{1\/4}}$$ O ( n 1\/4 ) approximation for densest k-subgraph. In: STOC, pp. 201\u2013210 (2010)","DOI":"10.1145\/1806689.1806719"},{"issue":"1","key":"357_CR4","doi-asserted-by":"crossref","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162(1), 439\u2013485 (2005)","journal-title":"Ann. Math."},{"key":"357_CR5","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: STOC 2014, pp. 624\u2013633 (2014)","DOI":"10.1145\/2591796.2591884"},{"issue":"5","key":"357_CR6","doi-asserted-by":"crossref","first-page":"1129","DOI":"10.1137\/S0097539704443057","volume":"34","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Guruswami, V., Khot, S., Regev, O.: A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM J. Comput. 34(5), 1129\u20131146 (2005)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"357_CR7","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"357_CR8","doi-asserted-by":"crossref","unstructured":"Feige, U., Feige, U.: Relations between average case complexity and approximation complexity. In: STOC 2002, pp. 534\u2013543 (2002)","DOI":"10.1145\/509907.509985"},{"issue":"5","key":"357_CR9","doi-asserted-by":"crossref","first-page":"1608","DOI":"10.1137\/S0097539700381097","volume":"31","author":"E Halperin","year":"2002","unstructured":"Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput. 31(5), 1608\u20131623 (2002)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"357_CR10","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1006\/inco.1996.0040","volume":"126","author":"TR Hancock","year":"1996","unstructured":"Hancock, T.R., Jiang, T., Li, M., Tromp, J.: Lower bounds on learning decision lists and trees. Inf. Comput. 126(2), 114\u2013122 (1996)","journal-title":"Inf. Comput."},{"issue":"4","key":"357_CR11","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"357_CR12","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9, 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"357_CR13","unstructured":"Johnson, D.S., Szegedy, M.: What are the least tractable instances of max independent set? In: SODA 1999, pp. 927\u2013928 (1999)"},{"issue":"4","key":"357_CR14","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/1597036.1597045","volume":"5","author":"G Karakostas","year":"2009","unstructured":"Karakostas, G.: A better approximation ratio for the vertex cover problem. ACM Trans. Algorithms 5(4), 41 (2009). doi: 10.1145\/1597036.1597045","journal-title":"ACM Trans. Algorithms"},{"key":"357_CR15","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of 34th ACM Symposium on Theory of Computing, pp. 767\u2013775 (2002)","DOI":"10.1145\/510014.510017"},{"key":"357_CR16","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1137\/S0097539705447037","volume":"36","author":"S Khot","year":"2006","unstructured":"Khot, S.: Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput. 36, 1025\u20131071 (2006)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"357_CR17","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"357_CR18","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1007\/s00453-001-0021-y","volume":"30","author":"G Kortsarz","year":"2001","unstructured":"Kortsarz, G.: On the hardness of approximating spanners. Algorithmica 30(3), 432\u2013450 (2001)","journal-title":"Algorithmica"},{"key":"357_CR19","unstructured":"Lov\u00e1sz, L.: Coverings and colorings of hypergraphs. In: Proceedings of the 4th Southeastern Conference on Combinatorics, Utilitas Mathematica, pp. 3\u201312 (1973)"},{"key":"357_CR20","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integral and fractional covers. Discrete Math. 13, 383\u2013390 (1975)","journal-title":"Discrete Math."},{"key":"357_CR21","doi-asserted-by":"crossref","unstructured":"Manurangsi, P.: Almost-polynomial ratio ETH-hardness of approximating densest $$k$$ k -subgraph. In: STOC 2017, pp. 954\u2013961 (2017)","DOI":"10.1145\/3055399.3055412"},{"key":"357_CR22","doi-asserted-by":"crossref","unstructured":"Moshkovitz, D., Raz, R.: Two query PCP with sub-constant error. In: FOCS 2008, pp. 314\u2013323 (2008)","DOI":"10.1109\/FOCS.2008.60"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0357-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0357-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0357-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,2]],"date-time":"2019-10-02T13:42:32Z","timestamp":1570023752000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0357-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,22]]},"references-count":22,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["357"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0357-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,8,22]]}}}