{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:45:32Z","timestamp":1764783932306,"version":"3.41.0"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319530062"},{"type":"electronic","value":"9783319530079"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-53007-9_23","type":"book-chapter","created":{"date-parts":[[2017,2,2]],"date-time":"2017-02-02T10:13:23Z","timestamp":1486030403000},"page":"254-266","source":"Crossref","is-referenced-by-count":7,"title":["Maximum Weighted Independent Sets with a Budget"],"prefix":"10.1007","author":[{"given":"Tushar","family":"Kalra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rogers","family":"Mathew","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sudebkumar Prasant","family":"Pal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vijay","family":"Pandey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,1,26]]},"reference":[{"key":"23_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/3-540-48777-8_2","volume-title":"Integer Programming and Combinatorial Optimization","author":"AA Ageev","year":"1999","unstructured":"Ageev, A.A., Sviridenko, M.I.: Approximation algorithms for maximum coverage and max cut with given sizes of parts. In: Cornu\u00e9jols, G., Burkard, R.E., Woeginger, G.J. (eds.) IPCO 1999. LNCS, vol. 1610, pp. 17\u201330. Springer, Heidelberg (1999). doi: 10.1007\/3-540-48777-8_2"},{"issue":"3","key":"23_CR2","doi-asserted-by":"crossref","first-page":"1137","DOI":"10.1137\/130931059","volume":"28","author":"N Apollonio","year":"2014","unstructured":"Apollonio, N., Simeone, B.: Improved approximation of maximum vertex coverage problem on bipartite graphs. SIAM J. Discret. Math. 28(3), 1137\u20131151 (2014)","journal-title":"SIAM J. Discret. Math."},{"key":"23_CR3","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.dam.2013.05.015","volume":"165","author":"N Apollonio","year":"2014","unstructured":"Apollonio, N., Simeone, B.: The maximum vertex coverage problem on bipartite graphs. Discret. Appl. Math. 165, 37\u201348 (2014)","journal-title":"Discret. Appl. Math."},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"Austrin, P., Khot, S., Safra, M.: Inapproximability of vertex cover and independent set in bounded degree graphs. In: 24th Annual IEEE Conference on Computational Complexity, CCC 2009, pp. 74\u201380. IEEE (2009)","DOI":"10.1109\/CCC.2009.38"},{"key":"23_CR5","unstructured":"Bandyapadhyay, S.: A variant of the maximum weight independent set problem. CoRR, abs\/1409.0173 (2014)"},{"issue":"2","key":"23_CR6","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1006\/jagm.2000.1150","volume":"39","author":"R Bar-Yehuda","year":"2001","unstructured":"Bar-Yehuda, R.: Using homogeneous weights for approximating the partial cover problem. J. Algorithms 39(2), 137\u2013144 (2001)","journal-title":"J. Algorithms"},{"key":"23_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-48523-6_17","volume-title":"Automata, Languages and Programming","author":"P Berman","year":"1999","unstructured":"Berman, P., Karpinski, M.: On some tighter inapproximability results (extended abstract). In: Wiedermann, J., Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 200\u2013209. Springer, Heidelberg (1999). doi: 10.1007\/3-540-48523-6_17"},{"issue":"2","key":"23_CR8","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/BF01994876","volume":"32","author":"R Boppana","year":"1992","unstructured":"Boppana, R., Halld\u00f3rsson, M.M.: Approximating maximum independent sets by excluding subgraphs. BIT Numer. Math. 32(2), 180\u2013196 (1992)","journal-title":"BIT Numer. Math."},{"key":"23_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/BFb0028569","volume-title":"STACS 98","author":"NH Bshouty","year":"1998","unstructured":"Bshouty, N.H., Burroughs, L.: Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem. In: Morvan, M., Meinel, C., Krob, D. (eds.) STACS 1998. LNCS, vol. 1373, pp. 298\u2013308. Springer, Heidelberg (1998). doi: 10.1007\/BFb0028569"},{"key":"23_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-662-44602-7_2","volume-title":"Theoretical Computer Science","author":"B Caskurlu","year":"2014","unstructured":"Caskurlu, B., Mkrtchyan, V., Parekh, O., Subramani, K.: On partial vertex cover and budgeted maximum coverage problems in bipartite graphs. In: Diaz, J., Lanese, I., Sangiorgi, D. (eds.) TCS 2014. LNCS, vol. 8705, pp. 13\u201326. Springer, Heidelberg (2014). doi: 10.1007\/978-3-662-44602-7_2"},{"issue":"1","key":"23_CR11","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.jalgor.2004.04.002","volume":"53","author":"R Gandhi","year":"2004","unstructured":"Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. J. Algorithms 53(1), 55\u201384 (2004)","journal-title":"J. Algorithms"},{"issue":"3","key":"23_CR12","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"23_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00020","volume":"4","author":"MM Halld\u00f3rsson","year":"2000","unstructured":"Halld\u00f3rsson, M.M.: Approximations of weighted independent set and hereditary subset problems. J. Graph Algorithms Appl. 4(1), 1\u201316 (2000)","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"23_CR14","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1016\/S0377-2217(02)00330-2","volume":"143","author":"Q Han","year":"2002","unstructured":"Han, Q., Ye, Y., Zhang, H., Zhang, J.: On approximation of max-vertex-cover. Eur. J. Oper. Res. 143(2), 342\u2013355 (2002)","journal-title":"Eur. J. Oper. Res."},{"key":"23_CR15","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $$n^{1-\\epsilon }$$ n 1 - \u03f5 . In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pp. 627\u2013636. IEEE (1996)","DOI":"10.1109\/SFCS.1996.548522"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-53007-9_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T23:07:36Z","timestamp":1749942456000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-53007-9_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319530062","9783319530079"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-53007-9_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}