{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T14:53:24Z","timestamp":1676472804821},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T00:00:00Z","timestamp":1330128000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2013,8]]},"DOI":"10.1007\/s10878-012-9464-0","type":"journal-article","created":{"date-parts":[[2012,2,24]],"date-time":"2012-02-24T17:16:52Z","timestamp":1330103812000},"page":"292-309","source":"Crossref","is-referenced-by-count":3,"title":["Tight approximation bounds for combinatorial frugal coverage algorithms"],"prefix":"10.1007","volume":"26","author":[{"given":"Ioannis","family":"Caragiannis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Kaklamanis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria","family":"Kyropoulou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,2,25]]},"reference":[{"issue":"3","key":"9464_CR1","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1007\/s00224-008-9112-3","volume":"45","author":"S Athanassopoulos","year":"2009","unstructured":"Athanassopoulos S, Caragiannis I, Kaklamanis C (2009a) Analysis of approximation algorithms for k-set cover using factor-revealing linear programs. Theory Comput Syst 45(3):555\u2013576","journal-title":"Theory Comput Syst"},{"key":"9464_CR2","series-title":"LNCS","first-page":"90","volume-title":"Proceedings of the 34th international symposium on mathematical foundations of computer science (MFCS)","author":"S Athanassopoulos","year":"2009","unstructured":"Athanassopoulos S, Caragiannis I, Kaklamanis C, Kyropoulou M (2009b) An improved approximation bound for spanning star forest and color saving. In: Proceedings of the 34th international symposium on mathematical foundations of computer science (MFCS). LNCS, vol 5734. Springer, Berlin, pp\u00a090\u2013101"},{"issue":"2","key":"9464_CR3","doi-asserted-by":"crossref","first-page":"959","DOI":"10.1137\/06067660X","volume":"23","author":"I Caragiannis","year":"2009","unstructured":"Caragiannis I (2009) Wavelength management in WDM rings to maximize the number of connections. SIAM J Discrete Math 23(2):959\u2013978","journal-title":"SIAM J Discrete Math"},{"key":"9464_CR4","first-page":"256","volume-title":"Proceedings of the 29th annual ACM symposium on theory of computing (STOC)","author":"R Duh","year":"1997","unstructured":"Duh R, F\u00fcrer M (1997) Approximation of k-set cover by semi-local optimization. In: Proceedings of the 29th annual ACM symposium on theory of computing (STOC), pp 256\u2013264"},{"issue":"4","key":"9464_CR5","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige U (1998) A threshold of lnn for approximating set cover. J ACM 45(4):634\u2013652","journal-title":"J ACM"},{"key":"9464_CR6","unstructured":"Feige U, Jozeph S (2010) Oblivious algorithms for the maximum directed cut problem. arXiv: 1010.0406"},{"key":"9464_CR7","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1007\/978-3-642-25591-5_50","volume-title":"Proceedings of the 22nd international symposium on algorithms and computation (ISAAC \u201911)","author":"M F\u00fcrer","year":"2011","unstructured":"F\u00fcrer M, Yu H (2011) Packing-based approximation algorithm for the k-set cover problem. In: Proceedings of the 22nd international symposium on algorithms and computation (ISAAC \u201911). LNCS, vol 7074. Springer, Berlin, pp\u00a0484\u2013493"},{"key":"9464_CR8","first-page":"227","volume-title":"Proceedings of the 29th IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS)","author":"C-C Huang","year":"2009","unstructured":"Huang C-C, Svitkina Z (2009) Donation center location problem. In: Proceedings of the 29th IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS), pp\u00a0227\u2013238"},{"issue":"1","key":"9464_CR9","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"CAJ Hurkens","year":"1989","unstructured":"Hurkens CAJ, Schrijver A (1989) On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J Discrete Math 2(1):68\u201372","journal-title":"SIAM J Discrete Math"},{"issue":"6","key":"9464_CR10","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1145\/950620.950621","volume":"50","author":"K Jain","year":"2003","unstructured":"Jain K, Mahdian M, Markakis E, Saberi A, Vazirani VV (2003) Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J ACM 50(6):795\u2013824","journal-title":"J ACM"},{"key":"9464_CR11","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson DS (1974) Approximation algorithms for combinatorial problems. J Comput Syst Sci 9:256\u2013278","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"9464_CR12","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1137\/060655225","volume":"23","author":"A Levin","year":"2008","unstructured":"Levin A (2008) Approximating the unweighted k-set cover problem: greedy meets local search. SIAM J Discrete Math 23(1):251\u2013264","journal-title":"SIAM J Discrete Math"},{"issue":"12\u201314","key":"9464_CR13","doi-asserted-by":"crossref","first-page":"1033","DOI":"10.1016\/j.tcs.2010.12.004","volume":"412","author":"A Levin","year":"2011","unstructured":"Levin A, Yovel U (2011) Uniform unweighted set cover: the power of non-oblivious local search. Theor Comput Sci 412(12\u201314):1033\u20131053","journal-title":"Theor Comput Sci"},{"key":"9464_CR14","first-page":"475","volume-title":"Proceedings of the 29th annual ACM symposium on theory of computing (STOC)","author":"R Raz","year":"1997","unstructured":"Raz R, Safra S (1997) A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th annual ACM symposium on theory of computing (STOC), pp 475\u2013484"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-012-9464-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-012-9464-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-012-9464-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:23:17Z","timestamp":1559276597000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-012-9464-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,25]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["9464"],"URL":"https:\/\/doi.org\/10.1007\/s10878-012-9464-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,25]]}}}