{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T20:59:37Z","timestamp":1725483577005},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424703"},{"type":"electronic","value":"9783540446668"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44666-4_7","type":"book-chapter","created":{"date-parts":[[2007,5,3]],"date-time":"2007-05-03T16:58:07Z","timestamp":1178211487000},"page":"24-36","source":"Crossref","is-referenced-by-count":5,"title":["On the Equivalence between the Primal-Dual Schema and the Local-Ratio Technique"],"prefix":"10.1007","author":[{"given":"Reuven","family":"Bar-Yehuda","sequence":"first","affiliation":[]},{"given":"Dror","family":"Rawitz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,17]]},"reference":[{"issue":"3","key":"7_CR1","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"12","author":"V. Bafna","year":"1999","unstructured":"V. Bafna, P. Berman, and T. Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. on Disc. Math., 12(3):289\u2013297, 1999.","journal-title":"SIAM J. on Disc. Math."},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"A. Bar-Noy, R. Bar-Yehuda, A. Freund, J. Naor, and B. Shieber. A unified approach to approximating resource allocation and scheduling. In 32nd ACM Symposium on the Theory of Computing, 2000.","DOI":"10.1145\/335305.335410"},{"issue":"2","key":"7_CR3","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s004530010009","volume":"27","author":"R. Bar-Yehuda","year":"2000","unstructured":"R. Bar-Yehuda. One for the price of two: A unified approach for approximating covering problems. Algorithmica, 27(2):131\u2013144, 2000.","journal-title":"Algorithmica"},{"key":"7_CR4","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R. Bar-Yehuda","year":"1981","unstructured":"R. Bar-Yehuda and S. Even. A linear time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 2:198\u2013203, 1981.","journal-title":"Journal of Algorithms"},{"key":"7_CR5","first-page":"27","volume":"25","author":"R. Bar-Yehuda","year":"1985","unstructured":"R. Bar-Yehuda and S. Even. A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics, 25:27\u201346, 1985.","journal-title":"Annals of Discrete Mathematics"},{"issue":"4","key":"7_CR6","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/s004530010075","volume":"29","author":"R. Bar-Yehuda","year":"2001","unstructured":"R. Bar-Yehuda and D. Rawitz. Efficient algorithms for bounded integer programs with two variables per constraint. Algorithmica, 29(4):595\u2013609, 2001.","journal-title":"Algorithmica"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"A. Becker and D. Geiger. Approximation algorithms for the loop cutset problem. In 10th Conference on Uncertainty in Artificial Intelligence, pages 60\u201368, 1994.","DOI":"10.1016\/B978-1-55860-332-5.50013-4"},{"issue":"4","key":"7_CR8","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1287\/opre.46.4.503","volume":"46","author":"D. Bertsimas","year":"1998","unstructured":"D. Bertsimas and C. Teo. From valid inequalities to heuristics: A unified view of primal-dual approximation algorithms in covering problems. Operations Research, 46(4):503\u2013514, 1998.","journal-title":"Operations Research"},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0167-6377(98)00021-2","volume":"22","author":"F. A. Chudak","year":"1998","unstructured":"F. A. Chudak, M. X. Goemans, D. S. Hochbaum, and D. P. Williamson. A primaldual interpretation of recent 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Operations Research Letters, 22:111\u2013118, 1998.","journal-title":"Operations Research Letters"},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"G. B. Dantzig, L. R. Ford, and D. R. Fulkerson. A primal-dual algorithm for linear programs. In H. W. Kuhn and A. W. Tucker, editors, Linear Inequalities and Related Systems, pages 171\u2013181. Princeton University Press, 1956.","DOI":"10.1515\/9781400881987-008"},{"key":"7_CR11","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269\u2013271, 1959.","journal-title":"Numerische Mathematik"},{"issue":"4","key":"7_CR12","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1137\/0205048","volume":"5","author":"S. Even","year":"1976","unstructured":"S. Even, A. Itai, and A. Shamir. On the complexity of timetable and multicommodity flow problems. SIAM J. on Comp., 5(4):691\u2013703, 1976.","journal-title":"SIAM J. on Comp."},{"key":"7_CR13","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"L. R. Ford","year":"1956","unstructured":"L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399\u2013404, 1956.","journal-title":"Canadian Journal of Mathematics"},{"issue":"2","key":"7_CR14","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"M. X. Goemans","year":"1995","unstructured":"M. X. Goemans and D. P. Williamson. A general approximation technique for constrained forest problems. SIAM J. on Comp., 24(2):296\u2013317, 1995.","journal-title":"SIAM J. on Comp."},{"key":"7_CR15","unstructured":"M. X. Goemans and D. P. Williamson. The primal-dual method for approximation algorithms and its application to network design problems. In [17], chapter 4."},{"key":"7_CR16","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/BF01758838","volume":"8","author":"D. Gusfield","year":"1992","unstructured":"D. Gusfield and L. Pitt. A bounded approximation for the minimum cost 2-SAT problem. Algorithmica, 8:103\u2013117, 1992.","journal-title":"Algorithmica"},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"D. S. Hochbaum, editor. Approximation Algorithms for NP-Hard Problem. PWS Publishing Company, 1997.","DOI":"10.1145\/261342.571216"},{"key":"7_CR18","unstructured":"D. S. Hochbaum. A framework of half integrality and good approximations. Manuscript, UC berkeley, 1997."},{"key":"7_CR19","doi-asserted-by":"crossref","unstructured":"K. Jain and V. V. Vazirani. Primal-dual approximation algorithms for metric facility location and k-median problems. In 40th IEEE Symposium on Foundations of Computer Science, pages 2\u201313, 1999.","DOI":"10.1109\/SFFCS.1999.814571"},{"key":"7_CR20","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"H. W. Kuhn","year":"1955","unstructured":"H. W. Kuhn. The Hungarian method of solving the assignment problem. Naval Research Logistics Quarterly, 2:83\u201397, 1955.","journal-title":"Naval Research Logistics Quarterly"},{"key":"7_CR21","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/BF01299747","volume":"15","author":"D. P. Williamson","year":"1995","unstructured":"D. P. Williamson, M. X. Goemans, M. Mihail, and V. V. Vazirani. A primal-dual approximation algorithm for generalized Steiner network problems. Combinatorica, 15:435\u2013454, 1995.","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44666-4_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T17:54:28Z","timestamp":1683827668000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44666-4_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424703","9783540446668"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-44666-4_7","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}