{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T22:40:16Z","timestamp":1739313616017,"version":"3.37.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,8,29]],"date-time":"2009-08-29T00:00:00Z","timestamp":1251504000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,6]]},"DOI":"10.1007\/s00453-009-9354-8","type":"journal-article","created":{"date-parts":[[2009,8,28]],"date-time":"2009-08-28T14:39:59Z","timestamp":1251470399000},"page":"421-450","source":"Crossref","is-referenced-by-count":2,"title":["Shape Rectangularization Problems in\u00a0Intensity-Modulated Radiation Therapy"],"prefix":"10.1007","volume":"60","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny Z.","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Don","family":"Coppersmith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaobo S.","family":"Hu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuang","family":"Luan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ewa","family":"Misio\u0142ek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chao","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,8,29]]},"reference":[{"key":"9354_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, A., Park, J.: Notes on searching in multidimensional monotone arrays. In: Proc. 29th Annual IEEE Symp. on Foundations of Computer Science, pp.\u00a0497\u2013512 (1988)","DOI":"10.1109\/SFCS.1988.21966"},{"key":"9354_CR2","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A. Aggarwal","year":"1987","unstructured":"Aggarwal, A., Klawe, M.M., Moran, S., Shor, P., Wilber, R.: Geometric applications of a matrix-searching algorithm. Algorithmica 2, 195\u2013208 (1987)","journal-title":"Algorithmica"},{"key":"9354_CR3","doi-asserted-by":"crossref","unstructured":"Aggarwal, A., Schieber, B., Tokuyama, T.: Finding a minimum-weight k-link path in graphs with the concave Monge property and applications. In: Proc. 9th Annual ACM Symp. on Computational Geometry pp.\u00a0189\u2013197 (1993)","DOI":"10.1145\/160985.161135"},{"key":"9354_CR4","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1002\/net.20047","volume":"45","author":"R.K. Ahuja","year":"2005","unstructured":"Ahuja, R.K., Hamacher, H.W.: A network flow algorithm to minimize beam-on time for unconstrained multileaf collimator problems in cancer radiation therapy. Networks 45, 36\u201341 (2005)","journal-title":"Networks"},{"key":"9354_CR5","unstructured":"Albers, S., Arora, S., Khanna, S.: Page replacement for general caching problems. In: Proc. 10th Annual ACM-SIAM Symp. on Discrete Algorithms, pp.\u00a031\u201340 (1999)"},{"key":"9354_CR6","doi-asserted-by":"crossref","unstructured":"Arkin, E.M., Mitchell, J.S.B., Narasimhan, G.: Resource-constrained geometric network optimization. In: Proc. 14th ACM Symp. on Computational Geometry, pp.\u00a0307\u2013316 (1998)","DOI":"10.1145\/276884.276919"},{"issue":"5","key":"9354_CR7","first-page":"753","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. J.\u00a0ACM 45(5), 753\u2013782 (1998)","journal-title":"J.\u00a0ACM"},{"key":"9354_CR8","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0020-0190(98)00010-6","volume":"65","author":"A. Arya","year":"1998","unstructured":"Arya, A., Ramesh, H.: A 2.5 factor approximation algorithm for the k-MST problem. Inf. Process. Lett. 65, 117\u2013118 (1998)","journal-title":"Inf. Process. Lett."},{"key":"9354_CR9","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1016\/j.dam.2005.04.008","volume":"152","author":"D. Baatar","year":"2005","unstructured":"Baatar, D., Ehrgott, M., Hamacher, H.W., Woeginger, G.J.: Decomposition of integer matrices and multileaf collimator sequencing. Discrete Appl. Math. 152, 6\u201334 (2005)","journal-title":"Discrete Appl. Math."},{"key":"9354_CR10","first-page":"1069","volume":"48","author":"A. Bar-Noy","year":"2001","unstructured":"Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Schieber, B.: A unified approach to approximating resource. J.\u00a0ACM 48, 1069\u20131090 (2001)","journal-title":"J.\u00a0ACM"},{"key":"9354_CR11","unstructured":"Bernstein, S.: Theory of Probability. Moscow (1927)"},{"issue":"4","key":"9354_CR12","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1002\/net.20007","volume":"43","author":"N. Boland","year":"2004","unstructured":"Boland, N., Hamacher, H.W., Lenzen, F.: Minimizing beam-on time in cancer radiation treatment using multileaf collimators. Networks 43(4), 226\u2013240 (2004)","journal-title":"Networks"},{"key":"9354_CR13","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1016\/0360-3016(94)90200-3","volume":"28","author":"T.R. Bortfeld","year":"1994","unstructured":"Bortfeld, T.R., Kahler, D.L., Waldron, T.J., Boyer, A.L.: X-ray field compensation with multileaf collimators. Int. J. Radiat. Oncol. Biol. Phys. 28, 723\u2013730 (1994)","journal-title":"Int. J. Radiat. Oncol. Biol. Phys."},{"key":"9354_CR14","unstructured":"Bruce, J.D.: Optimal quantization. PhD thesis, MIT, May 1964"},{"key":"9354_CR15","doi-asserted-by":"crossref","unstructured":"Chen, D.Z., Hu, X.S., Luan, S., Wang, C., Wu, X.: Mountain reduction, block matching, and applications in intensity-modulated radiation therapy. In: Proc. of 21th ACM Symposium on Computational Geometry, pp.\u00a035\u201344 (2005)","DOI":"10.1145\/1064092.1064101"},{"issue":"2\u20133","key":"9354_CR16","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1142\/S0218195906001999","volume":"16","author":"D.Z. Chen","year":"2006","unstructured":"Chen, D.Z., Hu, X.S., Luan, S., Naqvi, S.A., Wang, C., Yu, C.X.: Generalized geometric approaches for leaf sequencing problems in radiation therapy. Int. J. Comput. Geom. Appl. 16(2\u20133), 175\u2013204 (2006)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"7","key":"9354_CR17","doi-asserted-by":"crossref","first-page":"1147","DOI":"10.1118\/1.598081","volume":"24","author":"P.M. Evans","year":"1997","unstructured":"Evans, P.M., Hansen, V.N., Swindell, W.: The optimum intensities for multiple static collimator field compensation. Med. Phys. 24(7), 1147\u20131156 (1997)","journal-title":"Med. Phys."},{"key":"9354_CR18","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1002\/net.3230240103","volume":"24","author":"M. Fischetti","year":"1994","unstructured":"Fischetti, M., Hamacher, H.W., J\u00f8rnsten, K., Maffioli, F.: Weighted k-cardinality trees: complexity and polyhedral structure. Networks 24, 11\u201321 (1994)","journal-title":"Networks"},{"key":"9354_CR19","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Bentley, J., Tarjan, R.E.: Scaling and related techniques for geometric problems. In: Proc. 16th Annual ACM Symp. Theory of Computing, pp.\u00a0135\u2013143 (1984)","DOI":"10.1145\/800057.808675"},{"key":"9354_CR20","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"key":"9354_CR21","doi-asserted-by":"crossref","unstructured":"Garg, N.: A 3-approximation for the minimum tree spanning k vertices. In: Proc. 37th Annual IEEE Symp. on Foundations of Comp. Sci., pp.\u00a0302\u2013309 (1996)","DOI":"10.1109\/SFCS.1996.548489"},{"key":"9354_CR22","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"C.A.J. Hurkens","year":"1989","unstructured":"Hurkens, C.A.J., Schrijver, A.: 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, 68\u201372 (1989)","journal-title":"SIAM J. Discrete Math."},{"key":"9354_CR23","unstructured":"Lawler, E.: Combinatorial optimization: networks and matroids. Holt, Rinehart and Winston (1976)"},{"key":"9354_CR24","unstructured":"Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: a simple new method for the geometric k-MST problem. In: Proc. 7th Annual ACM-SIAM Symp. on Discrete Algorithms, pp.\u00a0402\u2013408 (1996)"},{"issue":"4","key":"9354_CR25","doi-asserted-by":"crossref","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"J.S.B. Mitchell","year":"1999","unstructured":"Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: Part II\u2014a simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput. 28(4), 1298\u20131309 (1999)","journal-title":"SIAM J. Comput."},{"key":"9354_CR26","unstructured":"Monge, G., D\u00e9blai et Remblai. In: M\u00e9mories de I\u2019Acad\u00e9mie des Sciences, Paris (1781)"},{"key":"9354_CR27","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"E. Petrank","year":"1994","unstructured":"Petrank, E.: The hardness of approximation: gap location. Comput. Complex. 4, 133\u2013157 (1994)","journal-title":"Comput. Complex."},{"key":"9354_CR28","unstructured":"Ravi, R., Sundaram, R., Marathe, M.V., Rosenkrantz, D.J., Ravi, S.S.: Spanning trees short and small. In: Proc. 5th Annual ACM-SIAM Symp. on Discrete Algorithms, pp. 546\u2013555 (1994)"},{"issue":"2","key":"9354_CR29","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1006\/jagm.1998.0955","volume":"29","author":"B. Schieber","year":"1998","unstructured":"Schieber, B.: Computing a minimum weight k-link path in graphs with the concave Monge property. J.\u00a0Algorithms 29(2), 204\u2013222 (1998)","journal-title":"J.\u00a0Algorithms"},{"key":"9354_CR30","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1145\/358841.358852","volume":"23","author":"J. Vuillemin","year":"1980","unstructured":"Vuillemin, J.: A unifying look at data structures. Commun. ACM 23, 229\u2013239 (1980)","journal-title":"Commun. ACM"},{"key":"9354_CR31","doi-asserted-by":"crossref","DOI":"10.1887\/0750302542","volume-title":"The Physics of Three-Dimensional Radiation Therapy","author":"S. Webb","year":"1993","unstructured":"Webb, S.: The Physics of Three-Dimensional Radiation Therapy. Institute of Physics Publishing, Bristol (1993)"},{"key":"9354_CR32","doi-asserted-by":"crossref","DOI":"10.1887\/0750303972","volume-title":"The Physics of Conformal Radiotherapy\u2014Advances in Technology","author":"S. Webb","year":"1997","unstructured":"Webb, S.: The Physics of Conformal Radiotherapy\u2014Advances in Technology. Institute of Physics Publishing, Bristol (1997)"},{"key":"9354_CR33","doi-asserted-by":"crossref","first-page":"663","DOI":"10.1016\/0196-6774(91)90039-2","volume":"12","author":"X. Wu","year":"1991","unstructured":"Wu, X.: Optimal quantization by matrix searching. J.\u00a0Algorithms 12, 663\u2013673 (1991)","journal-title":"J.\u00a0Algorithms"},{"key":"9354_CR34","unstructured":"Zelikovsky, A., Lozevanu, D.: Minimal and bounded trees. In: Tezele Cong. XVIII Acad. Romano-Americane, pp. 25\u201326. Kishinev (1993)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9354-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9354-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9354-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T22:21:24Z","timestamp":1739312484000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9354-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8,29]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,6]]}},"alternative-id":["9354"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9354-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2009,8,29]]}}}