{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:39:19Z","timestamp":1725557959091},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642143540"},{"type":"electronic","value":"9783642143557"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14355-7_12","type":"book-chapter","created":{"date-parts":[[2010,6,23]],"date-time":"2010-06-23T09:34:40Z","timestamp":1277285680000},"page":"112-118","source":"Crossref","is-referenced-by-count":0,"title":["Some Results on Incremental Vertex Cover Problem"],"prefix":"10.1007","author":[{"given":"Wenqiang","family":"Dai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"12_CR1","doi-asserted-by":"publisher","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. Journal of Algorithms\u00a039(2), 137\u2013144 (2001)","journal-title":"Journal of Algorithms"},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R. Bar-Yehuda","year":"1981","unstructured":"Bar-Yehuda, R., Even, S.: A linear time approximation algorithm for the weighted vertex cover problem. J. of Algorithms\u00a02, 198\u2013203 (1981)","journal-title":"J. of Algorithms"},{"key":"12_CR3","first-page":"27","volume":"25","author":"R. Bar-Yehuda","year":"1985","unstructured":"Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics\u00a025, 27\u201345 (1985)","journal-title":"Annals of Discrete Mathematics"},{"key":"12_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/BFb0028569","volume-title":"STACS 98","author":"N. Bshouty","year":"1998","unstructured":"Bshouty, N., Burroughs, L.: Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 298\u2013308. Springer, Heidelberg (1998)"},{"key":"12_CR5","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0020-0190(83)90007-8","volume":"16","author":"K.L. Clarkson","year":"1983","unstructured":"Clarkson, K.L.: A modification of the greedy algorithm for the vertex cover. Information Processing Letters\u00a016, 23\u201325 (1983)","journal-title":"Information Processing Letters"},{"key":"#cr-split#-12_CR6.1","doi-asserted-by":"crossref","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Annuals of Mathematics\u00a0162(1) (2005);","DOI":"10.4007\/annals.2005.162.439"},{"key":"#cr-split#-12_CR6.2","unstructured":"Preliminary version in STOC 2002 (2002)"},{"issue":"1","key":"12_CR7","doi-asserted-by":"publisher","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. Journal of Algorithms\u00a053(1), 55\u201384 (2004)","journal-title":"Journal of Algorithms"},{"issue":"4","key":"12_CR8","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. J. of ACM\u00a048(4), 798\u2013859 (2001)","journal-title":"J. of ACM"},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"Hartline, J., Sharp, A.: An Incremental Model for Combinatorial Minimization (2006), http:\/\/www.cs.cornell.edu\/~asharp","DOI":"10.1007\/11764298_4"},{"key":"12_CR10","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"D.S. Hochbaum","year":"1983","unstructured":"Hochbaum, D.S.: Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Applied Mathematics\u00a06, 243\u2013254 (1983)","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Hochbaum, D.S. (ed.): Approximation Algorithms for NP-hard Problems. PWS Publishing Company (1997)","DOI":"10.1145\/261342.571216"},{"key":"12_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BFb0053968","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"D.S. Hochbaum","year":"1998","unstructured":"Hochbaum, D.S.: The t-vertex cover problem: Extending the half integrality framework with budget constraints. In: Jansen, K., Rolim, J.D.P. (eds.) APPROX 1998. LNCS, vol.\u00a01444, pp. 111\u2013122. Springer, Heidelberg (1998)"},{"key":"12_CR13","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"12_CR14","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximaite to within 2\u2009\u2212\u2009\u03b5. In: Proceedings of the 18th IEEE Conference on Computational Complexity (2003)"},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"Lin, G.L., Nagarajan, C., Rajamaran, R., Williamson, D.P.: A general approach for incremental approximation and hierarchical clustering. In: Proc. 17th Symp. on Discrete Algorithms (SODA). ACM\/SIAM (2006)","DOI":"10.1145\/1109557.1109684"},{"key":"12_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1007\/11538462_16","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"J. Mestre","year":"2005","unstructured":"Mestre, J.: A primal-dual approximation algorithm for partial vertex cover: making educated guesses. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 182\u2013191. Springer, Heidelberg (2005)"},{"key":"12_CR17","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G.L. Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter Jr., L.E.: Vertex packings: Structural properties and algorithms. Mathematical Programming\u00a08, 232\u2013248 (1975)","journal-title":"Mathematical Programming"},{"key":"12_CR18","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14355-7_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T21:51:32Z","timestamp":1606168292000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14355-7_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642143540","9783642143557"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14355-7_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}