{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:57:00Z","timestamp":1725796620882},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319087825"},{"type":"electronic","value":"9783319087832"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08783-2_29","type":"book-chapter","created":{"date-parts":[[2014,7,5]],"date-time":"2014-07-05T10:04:30Z","timestamp":1404554670000},"page":"336-345","source":"Crossref","is-referenced-by-count":1,"title":["Primal-Dual Approximation Algorithms for Submodular Vertex Cover Problems with Linear\/Submodular Penalties"],"prefix":"10.1007","author":[{"given":"Dachuan","family":"Xu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fengmin","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenchen","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"29_CR1","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":"29_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. J. Algorithms\u00a02, 198\u2013203 (1981)","journal-title":"J. Algorithms"},{"key":"29_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. Ann. Discrete Math.\u00a025, 27\u201346 (1985)","journal-title":"Ann. Discrete Math."},{"key":"29_CR4","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/090773313","volume":"24","author":"R. Bar-Yehuda","year":"2010","unstructured":"Bar-Yehuda, R., Hermelin, D., Rawitz, D.: An Extension of the Nemhauser-Trotter Theorem to Generalized Vertex Cover with Applications. SIAM J. Discrete Math.\u00a024, 287\u2013300 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"29_CR5","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/050625382","volume":"19","author":"R. Bar-Yehuda","year":"2005","unstructured":"Bar-Yehuda, R., Rawitz, D.: On the Equivalence between the Primal-Dual Schema and the Local Technique. SIAM J. Discrete Math.\u00a019, 762\u2013797 (2005)","journal-title":"SIAM J. Discrete Math."},{"key":"29_CR6","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/BF01581256","volume":"59","author":"D. Bienstock","year":"1993","unstructured":"Bienstock, D., Goemans, M., Simchi-Levi, D., Williamson, D.: A Note on the Prize Collecting Traveling Salesman Problem. Math. Program.\u00a059, 413\u2013420 (1993)","journal-title":"Math. Program."},{"key":"29_CR7","first-page":"642","volume-title":"12th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"M. Charikar","year":"2001","unstructured":"Charikar, M., Khuller, S., Mount, D., Narasimhan, G.: Algorithms for Facility Location Problems with Outliers. In: 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 642\u2013651. SIAM Press, Washington SC (2001)"},{"key":"29_CR8","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/s00453-011-9526-1","volume":"63","author":"D. Du","year":"2012","unstructured":"Du, D., Lu, R., Xu, D.: A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties. Algorithmica\u00a063, 191\u2013200 (2012)","journal-title":"Algorithmica"},{"key":"29_CR9","first-page":"69","volume-title":"Combinatorial Structures and Their Applications (Proc. 1969 Calgary Conference)","author":"J. Edmonds","year":"1970","unstructured":"Edmonds, J.: Submodular Functions, Matroids, and Certain Polyhedra. In: Guy, R., Hanam, H., Sauer, N., Schonheim, J. (eds.) Combinatorial Structures and Their Applications (Proc. 1969 Calgary Conference), pp. 69\u201387. Gordon and Breach, New York (1970)"},{"key":"29_CR10","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/S0166-218X(02)00458-4","volume":"131","author":"L. Fleischer","year":"2003","unstructured":"Fleischer, L., Iwata, S.: A Push-Relabel Framework for Submodular Function Minimization and Applications to Parametric Optimization. Discrete Appl. Math.\u00a0131, 311\u2013322 (2003)","journal-title":"Discrete Appl. Math."},{"key":"29_CR11","volume-title":"Submodular Functions and Optimization","author":"S. Fujishige","year":"2005","unstructured":"Fujishige, S.: Submodular Functions and Optimization, 2nd edn. Elsevier, Amsterdam (2005)","edition":"2"},{"key":"29_CR12","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0196-6774(03)00053-1","volume":"48","author":"S. Guha","year":"2003","unstructured":"Guha, S., Hassin, R., Khuller, S., Or, E.: Capacitated Vertex Covering. J. Algorithms\u00a048, 257\u2013270 (2003)","journal-title":"J. Algorithms"},{"key":"29_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)"},{"key":"29_CR14","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A General Approximation Technique for Constrained Forest Problems. SIAM J. Comput.\u00a024, 296\u2013317 (1995)","journal-title":"SIAM J. Comput."},{"key":"29_CR15","doi-asserted-by":"publisher","first-page":"1608","DOI":"10.1137\/S0097539700381097","volume":"31","author":"E. Halperin","year":"2002","unstructured":"Halperin, E.: Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs. SIAM J. Comput.\u00a031, 1608\u20131623 (2002)","journal-title":"SIAM J. Comput."},{"key":"29_CR16","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"D.S. Hochbaum","year":"1982","unstructured":"Hochbaum, D.S.: Approximation Algorithms for the Set Covering and Vertex Cover Problems. SIAM J. Comput.\u00a011, 555\u2013556 (1982)","journal-title":"SIAM J. Comput."},{"key":"29_CR17","volume-title":"Approximation Algorithms for NP-hard Problems","author":"D.S. Hochbaum","year":"1997","unstructured":"Hochbaum, D.S.: Approximation Algorithms for NP-hard Problems. PWS Publishing Company, Boston (1997)"},{"key":"29_CR18","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/S0377-2217(02)00071-1","volume":"140","author":"D.S. Hochbaum","year":"2002","unstructured":"Hochbaum, D.S.: Solving Integer Programs over Monotone Inequalities in Three Variables: a Framework of Half Integrality and Good Approximations. Eur. J. Oper. Res.\u00a0140, 291\u2013321 (2002)","journal-title":"Eur. J. Oper. Res."},{"key":"29_CR19","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"S. Iwata","year":"2001","unstructured":"Iwata, S., Fleischer, L., Fujishige, S.: A Combinatorial Strongly Polynomial Algorithm for Minimizing Submodular Functions. J. ACM\u00a048, 761\u2013777 (2001)","journal-title":"J. ACM"},{"key":"29_CR20","first-page":"671","volume-title":"50th Annual IEEE Symposium on Foundations of Computer Science","author":"S. Iwata","year":"2009","unstructured":"Iwata, S., Nagano, K.: Submodular Function Minimization under Covering Constraints. In: 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 671\u2013680. IEEE Press, Atlanta (2009)"},{"key":"29_CR21","doi-asserted-by":"crossref","unstructured":"Karakostas, G.: A Better Approximation Ratio for the Vertex Cover Problem. ACM Trans. on Algorithms 5, Article No. 41 (2009)","DOI":"10.1145\/1597036.1597045"},{"key":"29_CR22","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S. Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex Cover Might Be Hard to Approxmate to with 2\u2009\u2212\u2009\u03b5. J. Comput. Syst. Sci.\u00a074, 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"29_CR23","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Springer, US (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"29_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1007\/978-3-642-38768-5_27","volume-title":"Computing and Combinatorics","author":"Y. Li","year":"2013","unstructured":"Li, Y., Du, D., Xiu, N., Xu, D.: Improved Approximation Algorithms for the Facility Location Problems with Linear\/submodular Penalty. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol.\u00a07936, pp. 292\u2013303. Springer, Heidelberg (2013)"},{"key":"29_CR25","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-642-68874-4_10","volume-title":"Mathematical Programming The State of the Art","author":"L. Lov\u00e1sz","year":"1983","unstructured":"Lov\u00e1sz, L.: Submodular Functions and Convexity. In: Bachem, A., Grtschel, M., Korte, B. (eds.) Mathematical Programming The State of the Art, pp. 235\u2013257. Springer, Heidelberg (1983)"},{"key":"29_CR26","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A. Schrijver","year":"2000","unstructured":"Schrijver, A.: A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time. J. Comb. Theory B\u00a080, 346\u2013355 (2000)","journal-title":"J. Comb. Theory B"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08783-2_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T02:34:02Z","timestamp":1558924442000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08783-2_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319087825","9783319087832"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08783-2_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}