{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T18:36:16Z","timestamp":1769970976397,"version":"3.49.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,6]]},"DOI":"10.1007\/s00453-009-9358-4","type":"journal-article","created":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T17:25:56Z","timestamp":1251825956000},"page":"451-463","source":"Crossref","is-referenced-by-count":20,"title":["Improved Approximations for Guarding 1.5-Dimensional Terrains"],"prefix":"10.1007","volume":"60","author":[{"given":"Khaled","family":"Elbassioni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik","family":"Krohn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Domagoj","family":"Matijevi\u0107","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juli\u00e1n","family":"Mestre","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Domagoj","family":"\u0160everdija","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,9,2]]},"reference":[{"issue":"6","key":"9358_CR1","doi-asserted-by":"crossref","first-page":"1631","DOI":"10.1137\/S0097539704446384","volume":"36","author":"B. Ben-Moshe","year":"2007","unstructured":"Ben-Moshe, B., Katz, M.J., Mitchell, J.S.B.: A constant-factor approximation algorithm for optimal 1.5D terrain guarding. SIAM J. Comput. 36(6), 1631\u20131647 (2007)","journal-title":"SIAM J. Comput."},{"key":"9358_CR2","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01584535","volume":"2","author":"C. Berge","year":"1972","unstructured":"Berge, C.: Balanced matrices. Math. Program. 2, 19\u201331 (1972)","journal-title":"Math. Program."},{"issue":"4","key":"9358_CR3","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H. Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14(4), 463\u2013479 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"9358_CR4","unstructured":"Chen, D.Z., Estivill-Castro, V., Urrutia, J.: Optimal guarding of polygons and monotone chains. In: Proceedings of the 7th Canadian Conference on Computational Geometry, pp. 133\u2013138 (1995)"},{"key":"9358_CR5","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L., Varadarajan, K.R.: Improved approximation algorithms for geometric set cover. In: Proceedings of the 20th Symposium on Computational Geometry, pp. 135\u2013141 (2005)","DOI":"10.1145\/1064092.1064115"},{"key":"9358_CR6","unstructured":"Demaine, E.D., O\u2019Rourke, J.: Open problems: open problems from CCCG 2005. In: Proceedings of the 18th Canadian Conference on Computational Geometry, pp. 75\u201380 (2006)"},{"key":"9358_CR7","doi-asserted-by":"crossref","unstructured":"Elbassioni, K., Matijevi\u0107, D., Mestre, J., \u0160everdija, D.: Improved approximations for guarding 1.5-dimensional terrains. CoRR, abs\/0809.0159v1 (2008)","DOI":"10.1007\/s00453-009-9358-4"},{"key":"9358_CR8","doi-asserted-by":"crossref","unstructured":"Garg, N., K\u00f6nemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In: 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 300\u2013309 (1998)","DOI":"10.1109\/SFCS.1998.743463"},{"issue":"1","key":"9358_CR9","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1006\/jagm.2002.1221","volume":"43","author":"D.R. Gaur","year":"2002","unstructured":"Gaur, D.R., Ibaraki, T., Krishnamurti, R.: Constant ratio approximation algorithms for the rectangle stabbing problem and the rectilinear partitioning problem. J. Algorithms 43(1), 138\u2013152 (2002)","journal-title":"J. Algorithms"},{"issue":"4","key":"9358_CR10","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R.L. Graham","year":"1972","unstructured":"Graham, R.L.: An efficient algorithm for determining the convex hull of a finite planar set. Inf. Process. Lett. 1(4), 132\u2013133 (1972)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9358_CR11","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/j.orl.2007.11.002","volume":"36","author":"R. Hassin","year":"2008","unstructured":"Hassin, R., Segev, D.: Rounding to an integral program. Oper. Res. Lett. 36(3), 321\u2013326 (2008)","journal-title":"Oper. Res. Lett."},{"key":"9358_CR12","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1137\/0606070","volume":"6","author":"A.J. Hoffman","year":"1985","unstructured":"Hoffman, A.J., Kolen, A., Sakarovitch, M.: Totally-balanced and greedy matrices. SIAM J. Algebr. Discrete Methods 6, 721\u2013730 (1985)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"9358_CR13","doi-asserted-by":"crossref","unstructured":"King, J.: A 4-approximation algorithm for guarding 1.5-dimensional terrains. In: Proceedings of the 13th Latin American Symposium on Theoretical Informatics, pp. 629\u2013640 (2006)","DOI":"10.1007\/11682462_58"},{"key":"9358_CR14","unstructured":"King, J.: Errata on \u201cA 4-approximation algorithm for guarding 1.5-dimensional terrains\u201d. http:\/\/www.cs.mcgill.ca\/~jking\/papers\/4apx_latin.pdf"},{"key":"9358_CR15","unstructured":"King, J.: VC-dimension of visibility on terrains. In: Proceedings of the 20th Canadian Conference on Computational Geometry, pp. 27\u201330 (2008)"},{"key":"9358_CR16","unstructured":"Kolen, A.: Location problems on trees and in the rectilinear plane. Ph.D. thesis, Matematisch Centrum, Amsterdam (1982)"},{"key":"9358_CR17","doi-asserted-by":"crossref","unstructured":"Koufogiannakis, C., Young, N.E.: Beating simplex for fractional packing and covering linear programs. In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 494\u2013504 (2007)","DOI":"10.1109\/FOCS.2007.62"},{"key":"9358_CR18","doi-asserted-by":"crossref","unstructured":"Koufogiannakis, C., Young, N.E.: Beating simplex for fractional packing and covering linear programs. CoRR, abs\/0801.1987 (2008)","DOI":"10.1109\/FOCS.2007.62"},{"key":"9358_CR19","unstructured":"Krohn, E.: Survey of terrain guarding and art gallery problems. Unpublished manuscript. (November 2007)"},{"key":"9358_CR20","unstructured":"Mestre, J.: Lagrangian relaxation and partial cover (extended abstract). In: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, pp. 539\u2013550 (2008)"},{"key":"9358_CR21","doi-asserted-by":"crossref","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9.: Fast approximation algorithms for fractional packing and covering problems. In: 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 495\u2013504 (1991)","DOI":"10.1109\/SFCS.1991.185411"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/s00453-009-9358-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T23:07:48Z","timestamp":1739315268000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9358-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,2]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,6]]}},"alternative-id":["9358"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9358-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9,2]]}}}