{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:53:12Z","timestamp":1725558792569},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642140303"},{"type":"electronic","value":"9783642140310"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14031-0_26","type":"book-chapter","created":{"date-parts":[[2010,6,28]],"date-time":"2010-06-28T09:50:06Z","timestamp":1277718606000},"page":"226-234","source":"Crossref","is-referenced-by-count":0,"title":["Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Berman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Aronov, B., Ezra, E., Sharir, M.: Small-size \u03b5-Nets for Axis-Parallel Rectangles and Boxes. In: Proc. STOC 2009 (2009)","DOI":"10.1145\/1536414.1536501"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"Bao, L., Garcia-Luna-Aceves, J.: Transmission scheduling in ad hoc networks with directional antennas. In: Proc. ACM MOBICOM 2002, pp. 48\u201358 (2002)","DOI":"10.1145\/570645.570652"},{"key":"26_CR3","doi-asserted-by":"crossref","unstructured":"Berman, P., Kasiviswanathan, S.P., Urgaonkar, B.: Packing to Angles and Sectors. In: Proc. SPAA 2007 (2007)","DOI":"10.1145\/1248377.1248405"},{"key":"26_CR4","unstructured":"Broden, B., Hammar, M., Nilsson, B.J.: Guarding Lines and 2-Link Polygons is APX-Hard. In: Proc. CCCG 2001 (2001)"},{"issue":"4","key":"26_CR5","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 and Computational Geometry\u00a014(4), 463\u2013479 (1995)","journal-title":"Discrete and Computational Geometry"},{"key":"26_CR6","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L., Varadarajan, K.R.: Improved approximation algorithms for vertex cover. In: Proc. ACM SoCG 2005, pp. 135\u2013141 (2005)","DOI":"10.1145\/1064092.1064115"},{"key":"26_CR7","unstructured":"Coffman, E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-hard problems, pp. 46\u201393. PWS Publishing (1997)"},{"key":"26_CR8","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"1990","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. The MIT Press, Cambridge (1990)"},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Erlabach, T., Jansen, K., Seidel, E.: Polynomial-Time Approximation Schemes for Geometric Intersection Graphs. SIAM J. Comput.\u00a034(6), 1302\u20131323","DOI":"10.1137\/S0097539702402676"},{"key":"26_CR10","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0097-3165(76)90001-7","volume":"21","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S., Yao, A.C.: Resource constrained scheduling as generalized bin-packing. J. Comb. Th. Ser. A\u00a021, 257\u2013298 (1976); cited from Coffman, E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-hard Problems, p. 50","journal-title":"J. Comb. Th. Ser. A"},{"key":"26_CR11","volume-title":"Computers and Intractability. A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"2003","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-completeness. W.H. Freeman and Company, New York (2003)"},{"issue":"1","key":"26_CR12","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"D.S. Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing in image processing and VLSI. Journal of the ACM\u00a032(1), 130\u2013136 (1985)","journal-title":"Journal of the ACM"},{"issue":"1","key":"26_CR13","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D.S. Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. Journal of the ACM\u00a034(1), 144\u2013162 (1987)","journal-title":"Journal of the ACM"},{"issue":"2","key":"26_CR14","first-page":"349","volume":"66","author":"H. Kellerer","year":"2003","unstructured":"Kellerer, H., Pfershy, U., Speranza, M.: An Efficient Approximation Scheme for the Subset Sum Problem. JCSS\u00a066(2), 349\u2013370 (2003)","journal-title":"JCSS"},{"issue":"1","key":"26_CR15","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1023\/B:JOCO.0000021934.29833.6b","volume":"8","author":"H. Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U.: Improved Dynamic Programming in Connection with an FPTAS for the Knapsack Problem. J. Comb. Optim.\u00a08(1), 5\u201311 (2004)","journal-title":"J. Comb. Optim."},{"key":"26_CR16","unstructured":"M.\u00a0Patrascu. Personnal Communication (August. 2009)"},{"key":"26_CR17","doi-asserted-by":"crossref","unstructured":"Peraki, C., Servetto, S.: On the maximum stable throughput problem in random networks with directional antennas. In: Proc. ACM MobiHoc 2003, pp. 76\u201387 (2003)","DOI":"10.1145\/778415.778426"},{"key":"26_CR18","doi-asserted-by":"crossref","unstructured":"Spyropoulos, A., Raghavendra, C.S.: Energy efficient communication in ad hoc networks using directional antennas. In: Proc. IEEE INFOCOM 2002 (2002)","DOI":"10.1109\/INFCOM.2002.1019263"},{"key":"26_CR19","doi-asserted-by":"crossref","unstructured":"Yi, S., Pei, Y., Kalyanaraman, S.: On the capacity improvement of ad hoc wireless networks using directional antennas. In: Proc. ACM MobiHoc 2003, pp. 108\u2013116 (2003)","DOI":"10.1145\/778415.778429"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14031-0_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:46:42Z","timestamp":1606186002000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14031-0_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642140303","9783642140310"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14031-0_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}