{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T21:14:50Z","timestamp":1760044490987},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319084039"},{"type":"electronic","value":"9783319084046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08404-6_31","type":"book-chapter","created":{"date-parts":[[2014,6,25]],"date-time":"2014-06-25T03:55:08Z","timestamp":1403668508000},"page":"357-367","source":"Crossref","is-referenced-by-count":4,"title":["Approximation Algorithms for Hitting Triangle-Free Sets of Line Segments"],"prefix":"10.1007","author":[{"given":"Anup","family":"Joshi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N. S.","family":"Narayanaswamy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N.: A non-linear lower bound for planar epsilon-nets. In: 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 341\u2013346 (2010)","DOI":"10.1109\/FOCS.2010.39"},{"issue":"1","key":"31_CR2","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for np-complete problems on planar graphs. J. ACM\u00a041(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"31_CR3","doi-asserted-by":"crossref","unstructured":"Balaban, I.J.: An optimal algorithm for finding segments intersections. In: Proceedings of the Eleventh Annual Symposium on Computational Geometry, SCG 1995, pp. 211\u2013219. ACM, New York (1995)","DOI":"10.1145\/220279.220302"},{"key":"31_CR4","doi-asserted-by":"crossref","unstructured":"Bentley, J., Ottmann, T.: Algorithms for reporting and counting geometric intersections. IEEE Transactions on Computers\u00a0C-28(9), 643\u2013647 (1979)","DOI":"10.1109\/TC.1979.1675432"},{"issue":"8","key":"31_CR5","doi-asserted-by":"publisher","first-page":"1653","DOI":"10.1080\/00207160.2013.775423","volume":"90","author":"V.E. Brimkov","year":"2013","unstructured":"Brimkov, V.E.: Approximability issues of guarding a set of segments. Int. J. Comput. Math.\u00a090(8), 1653\u20131667 (2013)","journal-title":"Int. J. Comput. Math."},{"issue":"15","key":"31_CR6","doi-asserted-by":"publisher","first-page":"1313","DOI":"10.1016\/j.tcs.2010.08.014","volume":"412","author":"V.E. Brimkov","year":"2011","unstructured":"Brimkov, V.E., Leach, A., Mastroianni, M., Wu, J.: Guarding a set of line segments in the plane. Theoretical Computer Science\u00a0412(15), 1313\u20131324 (2011)","journal-title":"Theoretical Computer Science"},{"key":"31_CR7","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1016\/j.dam.2011.11.023","volume":"160","author":"V.E. Brimkov","year":"2011","unstructured":"Brimkov, V.E., Leach, A., Wu, J., Mastroianni, M.: Approximation algorithms for a geometric set cover problem. Discrete Applied Mathematics\u00a0160, 1039\u20131052 (2011)","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"31_CR8","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H. Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.: Almost optimal set covers in finite vc-dimension. Discrete and Computational Geometry\u00a014(1), 463\u2013479 (1995)","journal-title":"Discrete and Computational Geometry"},{"key":"31_CR9","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(86)90025-5","volume":"32","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B.: Reporting and counting segment intersections. Journal of Computer and System Sciences\u00a032, 156\u2013182 (1986)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"31_CR10","doi-asserted-by":"publisher","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\u00a045(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"31_CR11","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/BF03041066","volume":"57","author":"H. Furstenberg","year":"1991","unstructured":"Furstenberg, H., Katznelson, Y.: A density version of the hales-jewett theorem. Journal d\u2019Analyse Math\u00e9matique\u00a057(1), 64\u2013119 (1991)","journal-title":"Journal d\u2019Analyse Math\u00e9matique"},{"key":"31_CR12","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1145\/800119.803884","volume-title":"Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC 1974","author":"M.R. Garey","year":"1974","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified np-complete problems. In: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC 1974, pp. 47\u201363. ACM, New York (1974)"},{"key":"31_CR13","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1145\/10515.10522","volume-title":"Proceedings of the Second Annual Symposium on Computational Geometry, SCG 1986","author":"D. Haussler","year":"1986","unstructured":"Haussler, D., Welzl, E.: Epsilon-nets and simplex range queries. In: Proceedings of the Second Annual Symposium on Computational Geometry, SCG 1986, pp. 61\u201371. ACM, New York (1986)"},{"key":"31_CR14","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility Among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"31_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"624","DOI":"10.1007\/3-540-45022-X_53","volume-title":"Automata, Languages and Programming","author":"V.S.A. Kumar","year":"2000","unstructured":"Kumar, V.S.A., Arya, S., Ramesh, H.: Hardness of set cover with intersection 1. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 624\u2013635. Springer, Heidelberg (2000)"},{"key":"31_CR16","first-page":"26","volume-title":"Proceedings of the 7th International Workshop on Algorithms and Data Structures, WADS 2001","author":"P.M. Long","year":"2001","unstructured":"Long, P.M.: Using the pseudo-dimension to analyze approximation algorithms for integer programming. In: Proceedings of the 7th International Workshop on Algorithms and Data Structures, WADS 2001, pp. 26\u201337. Springer, London (2001)"},{"issue":"5","key":"31_CR17","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/0167-6377(82)90039-6","volume":"1","author":"N. Megiddo","year":"1982","unstructured":"Megiddo, N., Tamir, A.: On the complexity of locating linear facilities in the plane. Operations Research Letters\u00a01(5), 194\u2013197 (1982)","journal-title":"Operations Research Letters"},{"issue":"4","key":"31_CR18","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1007\/s00454-010-9285-9","volume":"44","author":"N.H. Mustafa","year":"2010","unstructured":"Mustafa, N.H., Ray, S.: Improved results on geometric hitting set problems. Discrete & Computational Geometry\u00a044(4), 883\u2013895 (2010)","journal-title":"Discrete & Computational Geometry"},{"key":"31_CR19","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1145\/1377676.1377708","volume-title":"Proceedings of the Twenty-fourth Annual Symposium on Computational Geometry, SCG 2008","author":"E. Pyrga","year":"2008","unstructured":"Pyrga, E., Ray, S.: New existence proofs for \u03b5-nets. In: Proceedings of the Twenty-fourth Annual Symposium on Computational Geometry, SCG 2008, pp. 199\u2013207. ACM, New York (2008)"},{"key":"31_CR20","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall (September 2000)"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08404-6_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T03:58:08Z","timestamp":1558929488000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08404-6_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319084039","9783319084046"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08404-6_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}