{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:28:07Z","timestamp":1750307287594,"version":"3.41.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2011,7,1]],"date-time":"2011-07-01T00:00:00Z","timestamp":1309478400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2011,7]]},"abstract":"<jats:p>\n            We define an algorithmic paradigm, the stack model, that captures many primal-dual and local-ratio algorithms for approximating covering and packing problems. The stack model is defined syntactically and without any complexity limitations and hence our approximation bounds are independent of the\n            <jats:italic>P<\/jats:italic>\n            versus\n            <jats:italic>NP<\/jats:italic>\n            question. Using the stack model, we bound the performance of a broad class of primal-dual and local-ratio algorithms and supply a (log\n            <jats:italic>n<\/jats:italic>\n            +1)\/2 inapproximability result for set cover, a 4\/3 inapproximability for min Steiner tree, and a 0.913 inapproximability for interval scheduling on two machines.\n          <\/jats:p>","DOI":"10.1145\/1978782.1978784","type":"journal-article","created":{"date-parts":[[2011,7,21]],"date-time":"2011-07-21T13:27:09Z","timestamp":1311254829000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["How well can primal-dual and local-ratio algorithms perform?"],"prefix":"10.1145","volume":"7","author":[{"given":"Allan","family":"Borodin","sequence":"first","affiliation":[{"name":"University of Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Cashman","sequence":"additional","affiliation":[{"name":"Altera Corporation, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avner","family":"Magen","sequence":"additional","affiliation":[{"name":"University of Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,7,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31833-0_18"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"e_1_2_1_3_1","volume-title":"-Y","author":"Akcoglu K.","year":"2000","unstructured":"Akcoglu , K. , Aspnes , J. , Dasgupta , B. , and Kao , M . -Y . 2000 . Opportunity cost algorithms for combinatorial auctions. CoRR cs.CE\/0010031, 143--167. Akcoglu, K., Aspnes, J., Dasgupta, B., and Kao, M.-Y. 2000. Opportunity cost algorithms for combinatorial auctions. CoRR cs.CE\/0010031, 143--167."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2005.32"},{"volume-title":"Proceedings of the 27th Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom'08)","author":"Amzallag D.","key":"e_1_2_1_5_1","unstructured":"Amzallag , D. , Bar-Yehuda , R. , Raz , D. , and Scalosub , G . 2008. Cell selection in 4g cellular networks . In Proceedings of the 27th Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom'08) . 700--708. Amzallag, D., Bar-Yehuda, R., Raz, D., and Scalosub, G. 2008. Cell selection in 4g cellular networks. In Proceedings of the 27th Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom'08). 700--708."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1113-2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90037-0"},{"volume-title":"Proceedings of the 43rd Annual IEEE Conference on Foundations of Computer Science. IEEE Computer Society","author":"Arora S.","key":"e_1_2_1_8_1","unstructured":"Arora , S. , Bollobas , B. , and Lovasz , L . 2002. Proving integrality gaps without knowing the linear program . In Proceedings of the 43rd Annual IEEE Conference on Foundations of Computer Science. IEEE Computer Society , Los Alamitos, CA, 313--322. Arora, S., Bollobas, B., and Lovasz, L. 2002. Proving integrality gaps without knowing the linear program. In Proceedings of the 43rd Annual IEEE Conference on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, CA, 313--322."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a002"},{"volume-title":"Proceedings of the International Symposium on Algorithms and Computation (ISAAC'95)","author":"Bafna V.","key":"e_1_2_1_10_1","unstructured":"Bafna , V. , Berman , P. , and Fujito , T . 1995. Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs . In Proceedings of the International Symposium on Algorithms and Computation (ISAAC'95) . 142--151. Bafna, V., Berman, P., and Fujito, T. 1995. Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC'95). 142--151."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/502102.502107"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1497290.1497294"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9121-7"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1041680.1041683"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90020-1"},{"volume-title":"Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics","author":"Bar-Yehuda R.","key":"e_1_2_1_16_1","unstructured":"Bar-Yehuda , R. , Halldorsson , M. M. , Naor , J. , Shachnai , H. , and Shapira , I . 2002. Scheduling split intervals . In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics , Philadelphia, PA, 732--741. Bar-Yehuda, R., Halldorsson, M. M., Naor, J., Shachnai, H., and Shapira, I. 2002. Scheduling split intervals. In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, Philadelphia, PA, 732--741."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/050625382"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2006.05.010"},{"volume-title":"Proceedings of the 10th Conference on Uncertainty in Artificial Intelligence. 60--68","author":"Becker A.","key":"e_1_2_1_19_1","unstructured":"Becker , A. and Geiger , D . 1994. Approximation algorithms for the loop cutset problem . In Proceedings of the 10th Conference on Uncertainty in Artificial Intelligence. 60--68 . Becker, A. and Geiger, D. 1994. Approximation algorithms for the loop cutset problem. In Proceedings of the 10th Conference on Uncertainty in Artificial Intelligence. 60--68."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0259-9_7"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335401"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.46.4.503"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1036-3"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118756.3119016"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806769"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 9th International Integer Programming and Combinatorial Optimization Conference (IPCO'02)","volume":"2337","author":"Calinescu G.","unstructured":"Calinescu , G. , Chakrabarti , A. , Karloff , H. , and Rabani , Y . 2002. Improved approximation algorithms for resource allocation . In Proceedings of the 9th International Integer Programming and Combinatorial Optimization Conference (IPCO'02) . Lecture Notes in Computer Science , vol. 2337 . Springer, 40--414. Calinescu, G., Chakrabarti, A., Karloff, H., and Rabani, Y. 2002. Improved approximation algorithms for resource allocation. In Proceedings of the 9th International Integer Programming and Combinatorial Optimization Conference (IPCO'02). Lecture Notes in Computer Science, vol. 2337. Springer, 40--414."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 13th Integer Programming and Combinatorial Optimization Conference (IPCO'08)","volume":"5035","author":"Chakrabarty D.","unstructured":"Chakrabarty , D. , Devanur , N. R. , and Vazirani , V. V . 2008. New geometry-inspired relaxations and algorithms for the metric steiner tree problem . In Proceedings of the 13th Integer Programming and Combinatorial Optimization Conference (IPCO'08) . Lecture Notes in Computer Science , vol. 5035 . Springer, 344--358. Chakrabarty, D., Devanur, N. R., and Vazirani, V. V. 2008. New geometry-inspired relaxations and algorithms for the metric steiner tree problem. In Proceedings of the 13th Integer Programming and Combinatorial Optimization Conference (IPCO'08). Lecture Notes in Computer Science, vol. 5035. Springer, 344--358."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13036-6_29"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536455"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.06.046"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(98)00021-2"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.28.6.1402"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9124-4"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1.3.181"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584082"},{"key":"e_1_2_1_36_1","unstructured":"Edmonds J. and Kwon J. 2009. A faster approximate minimum steiner tree algorithm. Based on J. Kwon's MCS thesis \u201cImproved results on models of greedy and primal-dual algorithms.\u201d http:\/\/www.cse.yorku.ca\/~jeff\/research\/students\/James\/thesis.pdf.  Edmonds J. and Kwon J. 2009. A faster approximate minimum steiner tree algorithm. Based on J. Kwon's MCS thesis \u201cImproved results on models of greedy and primal-dual algorithms.\u201d http:\/\/www.cse.yorku.ca\/~jeff\/research\/students\/James\/thesis.pdf."},{"volume-title":"Proceedings of the International Symposium on Algorithms and Computation (ISAAC). 228--240","author":"Erlebach T.","key":"e_1_2_1_37_1","unstructured":"Erlebach , T. and Spieksma , F. C. R. 2000. Simple algorithms for a weighted interval selection problem . In Proceedings of the International Symposium on Algorithms and Computation (ISAAC). 228--240 . Erlebach, T. and Spieksma, F. C. R. 2000. Simple algorithms for a weighted interval selection problem. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC). 228--240."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00291-2"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970240118X"},{"volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07)","author":"Fernandez de la Vega W.","key":"e_1_2_1_41_1","unstructured":"Fernandez de la Vega , W. and Kenyon-Mathieu , C . 2007. Linear programming relaxations of maxcut . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07) . Society for Industrial and Applied Mathematics, Philadelphia, PA, 53--61. Fernandez de la Vega, W. and Kenyon-Mathieu, C. 2007. Linear programming relaxations of maxcut. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07). Society for Industrial and Applied Mathematics, Philadelphia, PA, 53--61."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/080721479"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00335-0"},{"key":"e_1_2_1_45_1","volume-title":"SIGACT News","volume":"28","author":"Hochbaum D., Ed.","year":"1997","unstructured":"Hochbaum , D., Ed. 1997 . Approximation Algorithms for NP-Hard Problems . In SIGACT News , Vol. 28 . ACM, New York. Hochbaum, D., Ed. 1997. Approximation Algorithms for NP-Hard Problems. In SIGACT News, Vol. 28. ACM, New York."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795286612"},{"volume-title":"Proceedings of the 3rd MPS Conference on Integer Programming and Combinatorial Optimization (IPCO'93)","author":"Klein P.","key":"e_1_2_1_49_1","unstructured":"Klein , P. and Ravi , R . 1993. When cycles collapse: A general approximation technique for constrained two-connectivity problems . In Proceedings of the 3rd MPS Conference on Integer Programming and Combinatorial Optimization (IPCO'93) . Springer, 39--55. Klein, P. and Ravi, R. 1993. When cycles collapse: A general approximation technique for constrained two-connectivity problems. In Proceedings of the 3rd MPS Conference on Integer Programming and Combinatorial Optimization (IPCO'93). Springer, 39--55."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0289-2"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/0605024"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90066-X"},{"volume-title":"Proceedings of the Annual ACM\/SIAM Symposium on Discrete Algorithms (SODA'99)","author":"Rajagopalan S.","key":"e_1_2_1_53_1","unstructured":"Rajagopalan , S. and Vazirani , V . 1999. On the bidirected cut relaxation for the metric steiner tree problem . In Proceedings of the Annual ACM\/SIAM Symposium on Discrete Algorithms (SODA'99) . 742--751. Rajagopalan, S. and Vazirani, V. 1999. On the bidirected cut relaxation for the metric steiner tree problem. In Proceedings of the Annual ACM\/SIAM Symposium on Discrete Algorithms (SODA'99). 742--751."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258641"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101393155"},{"volume-title":"Proceedings of the Indo-US Workshop on Cooperative Research in Computer Science. 166--168","author":"Saran H.","key":"e_1_2_1_56_1","unstructured":"Saran , H. , Vazirani , V. , and Young , N . 1992. A primal-dual approach to approximation algorithms for network steiner problems . In Proceedings of the Indo-US Workshop on Cooperative Research in Computer Science. 166--168 . Saran, H., Vazirani, V., and Young, N. 1992. A primal-dual approach to approximation algorithms for network steiner problems. In Proceedings of the Indo-US Workshop on Cooperative Research in Computer Science. 166--168."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250836"},{"key":"e_1_2_1_58_1","volume-title":"Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX-RANDOM). Lecture Notes in Computer Science","volume":"6302","author":"Singh M.","unstructured":"Singh , M. and Talwar , K . 2010. Improving integrality gaps via chvatal-gomory rounding . In Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX-RANDOM). Lecture Notes in Computer Science , vol. 6302 . Springer. Singh, M. and Talwar, K. 2010. Improving integrality gaps via chvatal-gomory rounding. In Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX-RANDOM). Lecture Notes in Computer Science, vol. 6302. Springer."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0887"},{"volume-title":"Approximation Algorithms","author":"Vazirani V. V.","key":"e_1_2_1_60_1","unstructured":"Vazirani , V. V. 2001. Approximation Algorithms . Springer , New York . Vazirani, V. V. 2001. Approximation Algorithms. Springer, New York."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100262"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_64"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1978782.1978784","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1978782.1978784","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:37Z","timestamp":1750244377000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1978782.1978784"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7]]},"references-count":61,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["10.1145\/1978782.1978784"],"URL":"https:\/\/doi.org\/10.1145\/1978782.1978784","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2011,7]]},"assertion":[{"value":"2008-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-07-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}