{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:50:37Z","timestamp":1767340237582},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540742074"},{"type":"electronic","value":"9783540742081"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-74208-1_4","type":"book-chapter","created":{"date-parts":[[2007,8,27]],"date-time":"2007-08-27T14:52:26Z","timestamp":1188226346000},"page":"44-58","source":"Crossref","is-referenced-by-count":9,"title":["Improved Approximation Algorithms for the Spanning Star Forest Problem"],"prefix":"10.1007","author":[{"given":"Ning","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roee","family":"Engelberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C. Thach","family":"Nguyen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prasad","family":"Raghavendra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Atri","family":"Rudra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gyanit","family":"Singh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4_CR1","unstructured":"Agra, A., Cardoso, D., Cerfeira, O., Rocha, E.: A spanning star forest model for the diversity problem in automobile industry. In: ECCO XVIII, Minsk (May 2005)"},{"key":"4_CR2","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. John Wiley and Sons Inc., New York (1992)"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Berry, V., Guillemot, S., Nicholas, F., Paul, C.: On the approximation of computing evolutionary trees. In: Proceedings of the Eleventh Annual International Computing and Combinatorics Conference, pp. 115\u2013123 (2005)","DOI":"10.1007\/11533719_14"},{"issue":"4","key":"4_CR4","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Fiege","year":"1998","unstructured":"Fiege, U.: A threshold of ln n for approximating set cover. Journal of the ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"Journal of the ACM"},{"key":"4_CR5","unstructured":"Goemans, M.X.: Mathematical programming and approximation algorithms. Lecture at Udine School, Udine, Italy (1996)"},{"issue":"4","key":"4_CR6","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. Journal of the ACM\u00a048(4), 798\u2013859 (2001)","journal-title":"Journal of the ACM"},{"key":"4_CR7","unstructured":"Krauthgamer, R., Mehta, A., Rudra, A.: Pricing commodities, or how to sell when buyers have restricted valuations, (Manuscript, 2007)"},{"issue":"5","key":"4_CR8","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. Journal of the ACM\u00a041(5), 960\u2013981 (1994)","journal-title":"Journal of the ACM"},{"key":"4_CR9","unstructured":"Nguyen, C.T., Shen, J., Hou, M., Sheng, L., Miller, W., Zhang, L.: Approximating the spanning star forest problem and its applications to genomic sequence alignment. In: SODA, pp. 645\u2013654 (2007)"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Slav\u00edk, P.: A tight analysis of the greedy algorithm for set cover. In: STOC, pp. 435\u2013441 (1996)","DOI":"10.1145\/237814.237991"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74208-1_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T16:29:48Z","timestamp":1556814588000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74208-1_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540742074","9783540742081"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74208-1_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}