{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:03:56Z","timestamp":1725494636588},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540410041"},{"type":"electronic","value":"9783540452539"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-45253-2_20","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T21:06:25Z","timestamp":1194987985000},"page":"211-219","source":"Crossref","is-referenced-by-count":2,"title":["Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem"],"prefix":"10.1007","author":[{"given":"Daya Ram","family":"Gaur","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toshihide","family":"Ibaraki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ramesh","family":"Krishnamurti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,2,11]]},"reference":[{"issue":"5","key":"20_CR1","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1109\/TC.1987.1676942","volume":"C-36","author":"M. J. Berger","year":"1987","unstructured":"M. J. Berger and S. H. Bokhari. A partitioning strategy for nonuniform problems on multiprocessors. IEEE Transactions on Computers, C-36(5):570\u2013580, May 1987.","journal-title":"IEEE Transactions on Computers"},{"issue":"1","key":"20_CR2","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1109\/12.75137","volume":"C-37","author":"S. H. Bokhari","year":"1988","unstructured":"S. H. Bokhari. Partitioning problems in parallel, pipelined, and distributed computing. IEEE Transactions on Computers, C-37(1):48\u201357, January 1988.","journal-title":"IEEE Transactions on Computers"},{"key":"20_CR3","unstructured":"H. A. Choi and B. Narahari. Algorithms for mapping and partitioning chain structured parallal computations. In Proceedings of the International Conference on Parallel Processing, volume 1, pages 625\u2013628, August 1991."},{"key":"20_CR4","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"V. Chv\u00e1tal. A greedy heuristic for the set covering problem. Math. of Operations Research, 4:233\u2013235, 1979.","journal-title":"Math. of Operations Research"},{"key":"20_CR5","volume-title":"Solving Problems on Concurrent Processors: General Techniques and Regular Problems","author":"G. Fox","year":"1988","unstructured":"G. Fox, M. Johnson, G. Lyzenga, S. Otto, J. Salmon, and D. Walker. Solving Problems on Concurrent Processors: General Techniques and Regular Problems. Prentice Hall, Englewood Cliffs, New Jersey, 07632, 1988."},{"key":"20_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/BFb0030123","volume-title":"Proceedings of the Third International Workshop on Parallel Algorithms for Irregularly Structured Problems","author":"M. Grigni","year":"1996","unstructured":"M. Grigni and F Manne. On the complexity of the generalized block distribution. In Proceedings of the Third International Workshop on Parallel Algorithms for Irregularly Structured Problems, Lecture Notes in Computer Science, pages 319\u2013326. Springer-Verlag, 1996."},{"key":"20_CR7","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0166-218X(91)90011-K","volume":"30","author":"R. Hassin","year":"1991","unstructured":"R. Hassin and N. Megiddo. Approximation algorithms for hitting objects with straight lines. Discrete Applied Mathematics, 30:29\u201342, 1991.","journal-title":"Discrete Applied Mathematics"},{"key":"20_CR8","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"D. S. Hochbaum","year":"1982","unstructured":"D. S. Hochbaum. Approximation algorithms for the set covering and vertex cover problem. SIAM Journal on Computing, 11:555\u2013556, 1982.","journal-title":"SIAM Journal on Computing"},{"key":"20_CR9","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. S. Johnson","year":"1974","unstructured":"D. S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Science, 9:256\u2013278, 1974.","journal-title":"Journal of Computer and System Science"},{"key":"20_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"616","DOI":"10.1007\/3-540-63165-8_216","volume-title":"Proceedings of the 24th. International Colloquim on Automata, Languages and Programming","author":"S. Khanna","year":"1997","unstructured":"S. Khanna, S. Muthukrishnan, and S. Skiena. Efficient array partitioning. In Proceedings of the 24th. International Colloquim on Automata, Languages and Programming, Lecture Notes in Computer Science, pages 616\u2013626. Springer-Verlag, 1997."},{"key":"20_CR11","unstructured":"F. Manne and T. Sorevik. Structured partitioning of arrays. Technical Report CS-96-119, Dept. of Informatics, Univ. of Bergen, Norway, 1995."},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"G. Nemhauser and L. Wolsey. Integer and Combinatorial Optimization. Wiley-Interscience, 1988.","DOI":"10.1002\/9781118627372"},{"key":"20_CR13","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1006\/jpdc.1994.1126","volume":"23","author":"D. M. Nicol","year":"1994","unstructured":"D. M. Nicol. Rectilinear partitioning of irregular data parallel computations. Journal of Parallel and Distributed Computing, 23:119\u2013134, 1994.","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"3","key":"20_CR14","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1109\/12.76406","volume":"40","author":"D. M. Nicol","year":"1991","unstructured":"D. M. Nicol and D. R. O\u2019Hallaron. Improved algorithms for mappimg parallel and pipelined computations. IEEE Transactions on Computers, 40(3):295\u2013306, 1991.","journal-title":"IEEE Transactions on Computers"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45253-2_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,25]],"date-time":"2019-02-25T08:08:31Z","timestamp":1551082111000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45253-2_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540410041","9783540452539"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-45253-2_20","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}