{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:04:39Z","timestamp":1725559479748},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540259206"},{"type":"electronic","value":"9783540320784"}],"license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11427186_7","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T17:38:24Z","timestamp":1279042704000},"page":"55-66","source":"Crossref","is-referenced-by-count":1,"title":["Rectangle Covers Revisited Computationally"],"prefix":"10.1007","author":[{"given":"L.","family":"Heinrich-Litan","sequence":"first","affiliation":[]},{"given":"M. E.","family":"L\u00fcbbecke","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"6","key":"7_CR1","doi-asserted-by":"publisher","first-page":"1509","DOI":"10.1137\/S0097539799358835","volume":"32","author":"V.S. Anil Kumar","year":"2003","unstructured":"Anil Kumar, V.S., Ramesh, H.: Covering rectilinear polygons with axis-parallel rectangles. SIAM J. Comput.\u00a032(6), 1509\u20131541 (2003)","journal-title":"SIAM J. Comput."},{"unstructured":"Aupperle, L.J., Conn, H.E., Keil, J.M., O\u2019Rourke, J.: Covering orthogonal polygons with squares. In: Proc. 26th Allerton Conf. Commun. Control Comput., pp. 97\u2013106 (1988)","key":"7_CR2"},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF02579327","volume":"1","author":"C. Berge","year":"1981","unstructured":"Berge, C., Chen, C.C., Chv\u00e1tal, V., Seow, C.S.: Combinatorial properties of polyominoes. Combinatorica\u00a01, 217\u2013224 (1981)","journal-title":"Combinatorica"},{"issue":"4","key":"7_CR4","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/BF02523677","volume":"17","author":"P. Berman","year":"1997","unstructured":"Berman, P., DasGupta, B.: Complexities of efficient solutions of rectilinear polygon cover problems. Algorithmica\u00a017(4), 331\u2013356 (1997)","journal-title":"Algorithmica"},{"unstructured":"Bern, M., Eppstein, D.: Approximation algorithms for geometric problems. In: Hochbaum [12], ch.\u00a08, pp. 296\u2013345","key":"7_CR5"},{"key":"7_CR6","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1137\/0602042","volume":"2","author":"S. Chaiken","year":"1981","unstructured":"Chaiken, S., Kleitman, D.J., Saks, M., Shearer, J.: Covering regions by rectangles. SIAM J. Algebraic Discrete Methods\u00a02, 394\u2013410 (1981)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"7_CR7","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1006\/jagm.1994.1025","volume":"17","author":"J.C. Culberson","year":"1994","unstructured":"Culberson, J.C., Reckhow, R.A.: Covering polygons is hard. J. Algorithms\u00a017, 2\u201344 (1994)","journal-title":"J. Algorithms"},{"issue":"3","key":"7_CR8","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1137\/0402027","volume":"2","author":"D.S. Franzblau","year":"1989","unstructured":"Franzblau, D.S.: Performance guarantees on a sweep-line heuristic for covering rectilinear polygons with rectangles. SIAM J. Discrete Math.\u00a02(3), 307\u2013321 (1989)","journal-title":"SIAM J. Discrete Math."},{"unstructured":"Goemans, M.X., Williamson, D.P.: The primal-dual method for approximation algorithms and it application to network design problems. In: Hochbaum [12], ch.\u00a04","key":"7_CR9"},{"key":"7_CR10","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"7_CR11","first-page":"1","volume":"77","author":"S. Hannenhalli","year":"2002","unstructured":"Hannenhalli, S., Hubell, E., Lipshutz, R., Pevzner, P.A.: Combinatorial algorithms for design of DNA arrays. Adv. Biochem. Eng. Biotechnol.\u00a077, 1\u201319 (2002)","journal-title":"Adv. Biochem. Eng. Biotechnol."},{"volume-title":"Approximation Algorithms for NP-Hard Problems","year":"1996","unstructured":"Hochbaum, D.S. (ed.): Approximation Algorithms for NP-Hard Problems. PWS Publishing Co., Boston (1996)","key":"7_CR12"},{"unstructured":"ILOG Inc., CPLEX Division. CPLEX 9.0 User\u2019s Manual (2004)","key":"7_CR13"},{"key":"7_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/3-540-63248-4_3","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"C. Levcopoulos","year":"1997","unstructured":"Levcopoulos, C., Gudmundsson, J.: Approximation algorithms for covering polygons with squares and similar problems. In: Rolim, J.D.P. (ed.) RANDOM 1997. LNCS, vol.\u00a01269, pp. 27\u201341. Springer, Berlin (1997)"},{"issue":"2","key":"7_CR15","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0020-0190(94)00017-4","volume":"50","author":"F. Maire","year":"1994","unstructured":"Maire, F.: Polyominos and perfect graphs. Inform. Process. Lett.\u00a050(2), 57\u201361 (1994)","journal-title":"Inform. Process. Lett."},{"unstructured":"Masek, W.J.: Some NP-complete set covering problems. MIT, Cambridge (1979) (Unpublished manuscript)","key":"7_CR16"},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0022-0000(90)90017-F","volume":"40","author":"R. Motwani","year":"1989","unstructured":"Motwani, R., Raghunathan, A., Saran, H.: Covering orthogonal polygons with star polygons: The perfect graph approach. J. Comput. System Sci.\u00a040, 19\u201348 (1989)","journal-title":"J. Comput. System Sci."},{"key":"7_CR18","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1137\/0402033","volume":"2","author":"R. Motwani","year":"1989","unstructured":"Motwani, R., Raghunathan, A., Saran, H.: Perfect graphs and orthogonally convex covers. SIAM J. Discrete Math.\u00a02, 371\u2013392 (1989)","journal-title":"SIAM J. Discrete Math."},{"unstructured":"Ohtsuki, T.: Minimum dissection of rectilinear regions. In: Proc. 1982 IEEE Symp. on Circuits and Systems, Rome, pp. 1210\u20131213 (1982)","key":"7_CR19"},{"key":"7_CR20","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)"},{"key":"7_CR21","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)"}],"container-title":["Lecture Notes in Computer Science","Experimental and Efficient Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11427186_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T16:01:25Z","timestamp":1558281685000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11427186_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540259206","9783540320784"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/11427186_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}