{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:10:44Z","timestamp":1771035044148,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540441861","type":"print"},{"value":"9783540457534","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45753-4_10","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T11:37:09Z","timestamp":1187264229000},"page":"94-107","source":"Crossref","is-referenced-by-count":10,"title":["Approximating Min-sum Set Cover"],"prefix":"10.1007","author":[{"given":"Uriel","family":"Feige","sequence":"first","affiliation":[]},{"given":"L\u00e1szl\u00f3","family":"Lov\u00e1sz","sequence":"additional","affiliation":[]},{"given":"Prasad","family":"Tetali","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,10,4]]},"reference":[{"issue":"3","key":"10_CR1","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy. \u201cProof verification and the hardness of approximation problems\u201d. JACM 45(3):501\u2013555, 1998.","journal-title":"JACM"},{"key":"10_CR2","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1006\/inco.1997.2677","volume":"140","author":"A. Bar-Noy","year":"1998","unstructured":"A. Bar-Noy, M. Bellare, M. Halldorsson, H. Shachnai, T. Tamir. \u201cOn chromatic sums and distributed resource allocation.\u201d Information and Computation, 140:183\u2013202, 1998.","journal-title":"Information and Computation"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"A. Bar-Noy, M. Halldorsson, G. Kortsarz. \u201cA matched approximation bound for the sum of a greedy coloring\u201d. Information Processing Letters, 1999.","DOI":"10.1016\/S0020-0190(99)00104-0"},{"key":"10_CR4","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1080\/10556780108805818","volume":"15","author":"S. Burer","year":"2001","unstructured":"S. Burer and R. Monteiro. \u201cA projected gradient algorithm for solving the maxcut SDP relaxation\u201d. Optimization Methods and Software, 15 (2001) 175\u2013200.","journal-title":"Optimization Methods and Software"},{"issue":"4","key":"10_CR5","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"U. Feige. \u201cA threshold of ln n for approximating set cover\u201d. Journal of the ACM, 45(4), 634\u2013652, 1998.","journal-title":"Journal of the ACM"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"U. Feige, M. Halldorsson, G. Kortsarz, A. Srinivasan. \u201cApproximating the domatic number\u201d. Preliminary version in STOC 2000.","DOI":"10.1145\/335305.335321"},{"issue":"2","key":"10_CR7","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U. Feige","year":"1998","unstructured":"U. Feige and J. Kilian. \u201cZero knowledge and the chromatic number\u201d. Journal of Computer and System Sciences, 57(2):187\u2013199, 1998.","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1006\/jagm.2001.1183","volume":"41","author":"U. Feige","year":"2001","unstructured":"U. Feige and M. Langberg. \u201cApproximation algorithms for maximization problems arising in graph partitioning\u201d. Journal of Algorithms 41, 174\u2013211 (2001).","journal-title":"Journal of Algorithms"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"E. Halperin and U. Zwick. \u201cA unified framework for obtaining improved approximation algorithms for maximum graph bisection problems\u201d. In proceedings of IPCO, 2001.","DOI":"10.1007\/3-540-45535-3_17"}],"container-title":["Lecture Notes in Computer Science","Approximation Algorithms for Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45753-4_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T04:32:55Z","timestamp":1556771575000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45753-4_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441861","9783540457534"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/3-540-45753-4_10","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}