{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:08:58Z","timestamp":1725559738977},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540275800"},{"type":"electronic","value":"9783540316916"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11523468_76","type":"book-chapter","created":{"date-parts":[[2010,7,18]],"date-time":"2010-07-18T18:58:59Z","timestamp":1279479539000},"page":"943-955","source":"Crossref","is-referenced-by-count":12,"title":["How Well Can Primal-Dual and Local-Ratio Algorithms Perform?"],"prefix":"10.1007","author":[{"given":"Allan","family":"Borodin","sequence":"first","affiliation":[]},{"given":"David","family":"Cashman","sequence":"additional","affiliation":[]},{"given":"Avner","family":"Magen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"76_CR1","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1137\/S0097539792236237","volume":"24","author":"A. Agrawal","year":"1995","unstructured":"Agrawal, A., Klein, P., Ravi, R.: When trees collide: An approximation algorithm for the generalized steiner problem on networks. SICOMP\u00a024, 440\u2013465 (1995)","journal-title":"SICOMP"},{"key":"76_CR2","doi-asserted-by":"crossref","unstructured":"Angelopoulos, S., Borodin, A.: The power of priority algorithms for facility location and set cover (2002)","DOI":"10.1007\/3-540-45753-4_5"},{"key":"76_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(87)90037-0","volume":"18","author":"E.M. Arkin","year":"1987","unstructured":"Arkin, E.M., Silverberg, E.L.: Scheduling jobs with fixed start and end times. Disc. Appl. Math.\u00a018, 1\u20138 (1987)","journal-title":"Disc. Appl. Math."},{"key":"76_CR4","doi-asserted-by":"crossref","unstructured":"Arora, S., Bollob\u00e1s, B., Lov\u00e1sz, L.: Proving integrality gaps without knowing the linear program. In: Proceedings of the 43rd Annual IEEE Conference on Foundations of Computer Science, pp. 313\u2013322 (2002)","DOI":"10.1109\/SFCS.2002.1181954"},{"issue":"5","key":"76_CR5","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1145\/502102.502107","volume":"48","author":"A. Bar-Noy","year":"2001","unstructured":"Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Schieber, B.: A unified approach to approximating resource allocation and scheduling. JACM\u00a048(5), 1069\u20131090 (2001)","journal-title":"JACM"},{"key":"76_CR6","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/1041680.1041683","volume":"36","author":"R. Bar-Yehuda","year":"2004","unstructured":"Bar-Yehuda, R., Bendel, A., Freund, A., Rawitz, D.: Local ratio: A unified framework for approxmation algorithms in memoriam: Shimon even 1935-2004. Computing Surveys\u00a036, 422\u2013463 (2004)","journal-title":"Computing Surveys"},{"key":"76_CR7","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. Journal of Algorithms\u00a02, 198\u2013203 (1981)","journal-title":"Journal of Algorithms"},{"key":"76_CR8","unstructured":"Bar-Yehuda, R., Halldorsson, M.M., Naor, J., Shachnai, H., Shapira, I.: Scheduling split intervals. In: Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 732\u2013741 (2002)"},{"key":"76_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/3-540-44666-4_7","volume-title":"Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques","author":"R. Bar-Yehuda","year":"2001","unstructured":"Bar-Yehuda, R., Rawitz, D.: On the equivalence between the primal-dual schema and the local ratio technique. In: Goemans, M.X., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) RANDOM 2001 and APPROX 2001. LNCS, vol.\u00a02129, pp. 24\u201335. Springer, Heidelberg (2001)"},{"key":"76_CR10","doi-asserted-by":"crossref","unstructured":"Bar-Yehuda, R., Rawitz, D.: Using fractional primal-dual to schedule split intervals with demands (2004)","DOI":"10.1007\/11561071_63"},{"key":"76_CR11","unstructured":"Borodin, A., Nielsen, M.N., Rackoff, C. (Incremental) priority algorithms. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (2002)"},{"key":"76_CR12","unstructured":"Alekhnovich, M., Borodin, A., Buresh-Oppenheim, J., Impagliazzo, R., Magen, A., Pitassi, T.: Toward a model for backtracking and dynamic programming. Unpublished manuscript (2004)"},{"key":"76_CR13","unstructured":"Davis, S., Impagliazzo, R.: Models of greedy algorithms for graph problems. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (2004)"},{"key":"76_CR14","unstructured":"Erlebach, T., Spieksma, F.C.R.: Interval selection: Applications, algorithms, and lower bounds. Technical Report 152, Computer Engineering and Networks Laboratory, ETH (October 2002)"},{"key":"76_CR15","doi-asserted-by":"crossref","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. SICOMP\u00a024, 296\u2013317 (1995)","journal-title":"SICOMP"},{"key":"76_CR16","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K. Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.: Approximation algorithms for the metric facility location problem and k-median problem using the primal-dual schema and lagrangian relaxation. JACM\u00a048, 274\u2013299 (2001)","journal-title":"JACM"},{"key":"76_CR17","unstructured":"Klein, P., Ravi, R.: When cycles collapse: A general approximation technique for constrained two-connectivity problems. In: Proceedings of the Third MPS Conference on Integer Programming and Combinatorial Optimization, pp. 39\u201355 (1993)"},{"key":"76_CR18","unstructured":"Rajagopalan, Vazirani: On the bidirected cut relaxation for the metric steiner tree problem. In: SODA, pp. 742\u2013751 (1999)"},{"key":"76_CR19","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and sub-constant error-probability pcp characterization of np. In: Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, pp. 475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"key":"76_CR20","unstructured":"Robins, G., Zelikovsky, A.: Improved steiner tree approximation in graphs. In: SODA, pp. 770\u2013779 (2001)"},{"key":"76_CR21","unstructured":"Saran, H., Vazirani, V., Young, N.: A primal-dual approach to approximation algorithms for network steiner problems. In: Proceedings of the Indo-US workshop on Cooperative Research in Computer Science, pp. 166\u2013168 (1992)"},{"key":"76_CR22","doi-asserted-by":"crossref","unstructured":"Thimm, M.: On the approximability of the steiner tree problem. LNCS. Springer, Heidelberg (2001)","DOI":"10.1007\/3-540-44683-4_59"},{"key":"76_CR23","volume-title":"Approximation algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation algorithms. Springer, New York (2001)"},{"issue":"3","key":"76_CR24","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/s101070100262","volume":"91","author":"D.P. Williamson","year":"2002","unstructured":"Williamson, D.P.: The primal-dual method for approximation algorithms. Mathematical Programming, Series B\u00a091(3), 447\u2013478 (2002)","journal-title":"Mathematical Programming, Series B"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11523468_76.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:06:15Z","timestamp":1605643575000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11523468_76"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540275800","9783540316916"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/11523468_76","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}