{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:25Z","timestamp":1750308745318,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,11,1]],"date-time":"2008-11-01T00:00:00Z","timestamp":1225497600000},"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":[[2008,11]]},"abstract":"<jats:p>\n            The design and analysis of approximation algorithms for\n            <jats:italic>NP<\/jats:italic>\n            -hard problems is perhaps the most active research area in the theory of combinatorial algorithms. In this article, we study the notion of a\n            <jats:italic>combinatorial dominance guarantee<\/jats:italic>\n            as a way for assessing the performance of a given approximation algorithm. An\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) dominance bound is a guarantee that the heuristic always returns a solution not worse than at least\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) solutions. We give tight analysis of many heuristics, and establish novel and interesting dominance guarantees even for certain inapproximable problems and heuristic search algorithms. For example, we show that the maximal matching heuristic of VERTEX COVER offers a combinatorial dominance guarantee of 2\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            \u2212 (1.839 +\n            <jats:italic>o<\/jats:italic>\n            (1))\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            . We also give inapproximability results for most of the problems we discuss.\n          <\/jats:p>","DOI":"10.1145\/1435375.1435383","type":"journal-article","created":{"date-parts":[[2008,12,10]],"date-time":"2008-12-10T15:32:31Z","timestamp":1228923151000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Combinatorial dominance guarantees for problems with infeasible solutions"],"prefix":"10.1145","volume":"5","author":[{"given":"Daniel","family":"Berend","sequence":"first","affiliation":[{"name":"Ben-Gurion University, Beer Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steven S.","family":"Skiena","sequence":"additional","affiliation":[{"name":"Stony Brook University, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yochai","family":"Twitto","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Beer Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,12,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.09.003"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.13.1.56.9748"},{"volume-title":"Proceedings of the IEEE 36th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press","author":"Bellare M.","key":"e_1_2_1_3_1","unstructured":"Bellare , M. , Goldreich , O. , and Sudan , M . 1995. Free bits, PCPs, and non-approximability\u2014towards tight results . In Proceedings of the IEEE 36th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 422--431. Bellare, M., Goldreich, O., and Sudan, M. 1995. Free bits, PCPs, and non-approximability\u2014towards tight results. In Proceedings of the IEEE 36th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 422--431."},{"key":"e_1_2_1_4_1","unstructured":"Berend D. Skiena S. and Twitto Y. 2006. Dominance certificates for combinatorial optimization problems. submitted.  Berend D. Skiena S. and Twitto Y. 2006. Dominance certificates for combinatorial optimization problems. submitted."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050010"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2600392"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00359-7"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(01)00053-0"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00267-0"},{"key":"e_1_2_1_10_1","first-page":"223","article-title":"Exponential neighborhoods and domination analysis for the TSP. In The Traveling Salesman Problem and its Variations, G. Gutin and A. Punnen, Eds. Kluwer Academic Publishers, Boston","volume":"6","author":"Gutin G.","year":"2002","unstructured":"Gutin , G. , Yeo , A. , and Zverovich , A. 2002 a. Exponential neighborhoods and domination analysis for the TSP. In The Traveling Salesman Problem and its Variations, G. Gutin and A. Punnen, Eds. Kluwer Academic Publishers, Boston , Chapter 6 , 223 -- 256 . Gutin, G., Yeo, A., and Zverovich, A. 2002a. Exponential neighborhoods and domination analysis for the TSP. In The Traveling Salesman Problem and its Variations, G. Gutin and A. Punnen, Eds. Kluwer Academic Publishers, Boston, Chapter 6, 223--256.","journal-title":"Chapter"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00262-1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1187"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321909"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215020"},{"key":"e_1_2_1_15_1","first-page":"424","volume-title":"Lecture Notes in Computer Science","volume":"2748","author":"Phan V.","unstructured":"Phan , V. , Skiena , S. , and Sumazin , P . 2003. A model for analyzing black-box optimization . In Lecture Notes in Computer Science , vol. 2748 . Springer-Verlag, New York , pp. 424 -- 438 . Phan, V., Skiena, S., and Sumazin, P. 2003. A model for analyzing black-box optimization. In Lecture Notes in Computer Science, vol. 2748. Springer-Verlag, New York, pp. 424--438."},{"key":"e_1_2_1_16_1","unstructured":"Punnen A. Margot F. and Kabadi S. 2001. TSP heuristics: Domination analysis and complexity. Res. rep. 2001-06 Dept. of Mathematics Univ. Kentucky Mar.  Punnen A. Margot F. and Kabadi S. 2001. TSP heuristics: Domination analysis and complexity. Res. rep. 2001-06 Dept. of Mathematics Univ. Kentucky Mar."},{"key":"e_1_2_1_17_1","first-page":"18","article-title":"Estimates of the accuracy of procedures in the traveling salesman problem","volume":"4","author":"Rublineckii V.","year":"1973","unstructured":"Rublineckii , V. 1973 . Estimates of the accuracy of procedures in the traveling salesman problem . Num. Math. Comput. Tech. (in Russian) 4 , 18 -- 23 . Rublineckii, V. 1973. Estimates of the accuracy of procedures in the traveling salesman problem. Num. Math. Comput. Tech. (in Russian) 4, 18--23.","journal-title":"Num. Math. Comput. Tech. (in Russian)"},{"key":"e_1_2_1_18_1","first-page":"8","article-title":"The approximate solution of the traveling salesman problem by a local algorithm that searches neighborhoods of exponential cardinality in quadratic time. Softw","volume":"31","author":"Sarvanov V.","year":"1981","unstructured":"Sarvanov , V. , and Doroshko , N. 1981 a. The approximate solution of the traveling salesman problem by a local algorithm that searches neighborhoods of exponential cardinality in quadratic time. Softw .: Algor. Prog. (in Russian) 31 , 8 -- 11 . Sarvanov, V., and Doroshko, N. 1981a. The approximate solution of the traveling salesman problem by a local algorithm that searches neighborhoods of exponential cardinality in quadratic time. Softw.: Algor. Prog. (in Russian) 31, 8--11.","journal-title":"Algor. Prog. (in Russian)"},{"key":"e_1_2_1_19_1","first-page":"11","article-title":"The approximate solution of the traveling salesman problem by a local algorithm that searches neighborhoods of factorial cardinality in cubic time. Soft","volume":"31","author":"Sarvanov V.","year":"1981","unstructured":"Sarvanov , V. , and Doroshko , N. 1981 b. The approximate solution of the traveling salesman problem by a local algorithm that searches neighborhoods of factorial cardinality in cubic time. Soft .: Algor. Prog. (in Russian) 31 , 11 -- 13 . Sarvanov, V., and Doroshko, N. 1981b. The approximate solution of the traveling salesman problem by a local algorithm that searches neighborhoods of factorial cardinality in cubic time. Soft.: Algor. Prog. (in Russian) 31, 11--13.","journal-title":"Algor. Prog. (in Russian)"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01171114"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.3.319"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1435375.1435383","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1435375.1435383","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:16Z","timestamp":1750278136000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1435375.1435383"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,11]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,11]]}},"alternative-id":["10.1145\/1435375.1435383"],"URL":"https:\/\/doi.org\/10.1145\/1435375.1435383","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2008,11]]},"assertion":[{"value":"2006-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}