{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:32Z","timestamp":1759638272401,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030392185"},{"type":"electronic","value":"9783030392192"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-39219-2_23","type":"book-chapter","created":{"date-parts":[[2020,1,24]],"date-time":"2020-01-24T19:09:24Z","timestamp":1579892964000},"page":"269-281","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Minimum Satisfiability Problem"],"prefix":"10.1007","author":[{"given":"Umair","family":"Arif","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Benkoczi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daya Ram","family":"Gaur","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ramesh","family":"Krishnamurti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,1,24]]},"reference":[{"unstructured":"Arif, U.M.: On primal-dual schema for the minimum satisfiability problem. Master\u2019s thesis, University of Lethbridge, Canada (2017)","key":"23_CR1"},{"issue":"2","key":"23_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. Algorithms 2(2), 198\u2013203 (1981). ISSN 0196\u20136774","journal-title":"J. Algorithms"},{"key":"23_CR3","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S0304-0208(08)73101-3","volume":"109","author":"R Bar-Yehuda","year":"1985","unstructured":"Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. North-Holland Math. Stud. 109, 27\u201345 (1985)","journal-title":"North-Holland Math. Stud."},{"issue":"2","key":"23_CR4","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s002240000113","volume":"32","author":"P Berman","year":"1999","unstructured":"Berman, P., Fujito, T.: On approximation properties of the independent set problem for low degree graphs. Theory Comput. Syst. 32(2), 115\u2013132 (1999)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"23_CR5","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/S0167-6377(99)00010-3","volume":"24","author":"D Bertsimas","year":"1999","unstructured":"Bertsimas, D., Teo, C., Vohra, R.: On dependent randomized rounding algorithms. Oper. Res. Lett. 24(3), 105\u2013114 (1999)","journal-title":"Oper. Res. Lett."},{"issue":"1\u20133","key":"23_CR6","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0166-218X(92)90273-D","volume":"24","author":"J-M Bourjolly","year":"1989","unstructured":"Bourjolly, J.-M., Pulleyblank, W.R.: K\u00f6nig-Everv\u00e1ry graphs, 2-bicritical graphs and fractional matchings. Discrete Appl. Math. 24(1\u20133), 63\u201382 (1989)","journal-title":"Discrete Appl. Math."},{"doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC 1971, pp. 151\u2013158, New York, NY, USA. ACM (1971)","key":"23_CR7","DOI":"10.1145\/800157.805047"},{"key":"23_CR8","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162, 439\u2013485 (2005)","journal-title":"Ann. Math."},{"issue":"3","key":"23_CR9","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17(3), 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"issue":"4","key":"23_CR10","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"MX Goemans","year":"1994","unstructured":"Goemans, M.X., Williamson, D.P.: New $$\\frac{3}{4}$$-approximation algorithms for the maximum satisfiability problem. SIAM J. Discrete Math. 7(4), 656\u2013666 (1994)","journal-title":"SIAM J. Discrete Math."},{"issue":"5","key":"23_CR11","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. 31(5), 1608\u20131623 (2002)","journal-title":"SIAM J. Comput."},{"key":"23_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BFb0053967","volume-title":"Approximation Algorithms for Combinatiorial Optimization","author":"DS Hochbaum","year":"1998","unstructured":"Hochbaum, D.S.: Instant recognition of half integrality and 2-approximations. In: Jansen, K., Rolim, J. (eds.) APPROX 1998. LNCS, vol. 1444, pp. 99\u2013110. Springer, Heidelberg (1998). \nhttps:\/\/doi.org\/10.1007\/BFb0053967"},{"issue":"3","key":"23_CR13","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"DS Hochbaum","year":"1982","unstructured":"Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM J. Comput. 11(3), 555\u2013556 (1982)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"23_CR14","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"DS Hochbaum","year":"1983","unstructured":"Hochbaum, D.S.: Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Appl. Math. 6(3), 243\u2013254 (1983)","journal-title":"Discrete Appl. Math."},{"unstructured":"Iranmanesh, E.: Algorithms for Problems in Voting and Scheduling. Ph.D. thesis, Simon Fraser University (2016)","key":"23_CR15"},{"issue":"3","key":"23_CR16","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"23_CR17","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 approximate to within $$2- \\varepsilon $$. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"23_CR18","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1137\/S0895480191220836","volume":"7","author":"R Kohli","year":"1994","unstructured":"Kohli, R., Krishnamurti, R., Mirchandani, P.: The minimum satisfiability problem. SIAM J. Discret. Math. 7(2), 275\u2013283 (1994)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"23_CR19","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.disopt.2005.08.008","volume":"3","author":"R Krishnamurti","year":"2006","unstructured":"Krishnamurti, R., Gaur, D.R., Ghosh, S.K., Sachs, H.: Berge\u2019s theorem for the maximum charge problem. Discrete Optim. 3(2), 174\u2013178 (2006)","journal-title":"Discrete Optim."},{"issue":"1","key":"23_CR20","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0020-0190(96)00031-2","volume":"58","author":"M Marathe","year":"1996","unstructured":"Marathe, M., Ravi, S.: On approximation algorithms for the minimum satisfiability problem. Inf. Process. Lett. 58(1), 23\u201329 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"23_CR21","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF00290149","volume":"22","author":"B Monien","year":"1985","unstructured":"Monien, B., Speckenmeyer, E.: Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Informatica 22(1), 115\u2013123 (1985)","journal-title":"Acta Informatica"},{"doi-asserted-by":"crossref","unstructured":"Orlin, J.B.: Max flows in O(nm) time, or better. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 765\u2013774. ACM (2013)","key":"23_CR22","DOI":"10.1145\/2488608.2488705"},{"key":"23_CR23","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"CH Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Courier Corporation, North Chelmsford (1982)"},{"issue":"2","key":"23_CR24","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"E Tardos","year":"1986","unstructured":"Tardos, E.: A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res. 34(2), 250\u2013256 (1986)","journal-title":"Oper. Res."},{"unstructured":"Yannakakis, M.: On the approximation of maximum satisfiability. In: Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1992, pp. 1\u20139, Philadelphia, PA, USA (1992). ISBN 0-89791-466-X","key":"23_CR25"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-39219-2_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,25]],"date-time":"2020-01-25T00:02:06Z","timestamp":1579910526000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-39219-2_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030392185","9783030392192"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-39219-2_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"24 January 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CALDAM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Algorithms and Discrete Applied Mathematics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hyderabad","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 February 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 February 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"caldam2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.iith.ac.in\/~caldam2020\/index.php","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}