{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T20:53:41Z","timestamp":1725742421837},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642401633"},{"type":"electronic","value":"9783642401640"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40164-0_26","type":"book-chapter","created":{"date-parts":[[2013,7,21]],"date-time":"2013-07-21T21:01:30Z","timestamp":1374440490000},"page":"271-282","source":"Crossref","is-referenced-by-count":1,"title":["Domination Analysis of Algorithms for Bipartite Boolean Quadratic Programs"],"prefix":"10.1007","author":[{"given":"Abraham P.","family":"Punnen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piyashat","family":"Sripratak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Karapetyan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"26_CR1","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/j.jalgor.2003.09.003","volume":"50","author":"N. Alon","year":"2004","unstructured":"Alon, N., Gutin, G., Krivelevich, M.: Algorithms with large domination ratio. Journal on Algorithms\u00a050, 118\u2013131 (2004)","journal-title":"Journal on Algorithms"},{"key":"26_CR2","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1137\/S0097539704441629","volume":"35","author":"N. Alon","year":"2006","unstructured":"Alon, N., Naor, A.: Approximating the cut-norm via Grothendieck\u2019s inequality. SIAM Journal of Computing\u00a035, 787\u2013803 (2006)","journal-title":"SIAM Journal of Computing"},{"key":"26_CR3","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1137\/080729256","volume":"40","author":"C. Amb\u00fchl","year":"2011","unstructured":"Amb\u00fchl, C., Mastrolilli, M., Svensson, O.: Inapproximability results for maximum edge biclique, minimum linear arrangement, and sparsest cut. SIAM Journal of Computing\u00a040, 567\u2013596 (2011)","journal-title":"SIAM Journal of Computing"},{"key":"26_CR4","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/S0166-218X(97)00129-7","volume":"82","author":"E. Angel","year":"1995","unstructured":"Angel, E., Zissimopoulos, V.: On the quality of local search for the quadratic assignment problem. Discrete Applied Mathematics\u00a082, 15\u201325 (1995)","journal-title":"Discrete Applied Mathematics"},{"key":"26_CR5","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1016\/j.disopt.2006.05.004","volume":"3","author":"G. Bendall","year":"2006","unstructured":"Bendall, G., Margot, F.: Minimum number of below average triangles in a weighted complete graph. Discrete Optimization\u00a03, 206\u2013219 (2006)","journal-title":"Discrete Optimization"},{"key":"26_CR6","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1145\/1435375.1435383","volume":"5","author":"D. Berend","year":"2008","unstructured":"Berend, D., Skiena, S., Twitto, Y.: Combinatorial dominance guarantees for problems with infeasible solutions. ACM Transactions on Algorithms 5, Article 8 (2008)","journal-title":"ACM Transactions on Algorithms"},{"key":"26_CR7","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0304-3975(97)00099-6","volume":"209","author":"M. Demange","year":"1998","unstructured":"Demange, M., Grisoni, P., Th, V.: Paschos, Differential approximation algorithms for some combinatorial optimization problems. Theoretical Computer Science\u00a0209, 107\u2013122 (1998)","journal-title":"Theoretical Computer Science"},{"key":"26_CR8","doi-asserted-by":"crossref","unstructured":"Deneko, V.G., Woeginger, G.J.: A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem. Mathematical Programming\u00a087(200), 519\u2013542","DOI":"10.1007\/s101070050010"},{"key":"26_CR9","doi-asserted-by":"publisher","first-page":"1149","DOI":"10.1137\/110820361","volume":"32","author":"N. Gillis","year":"2011","unstructured":"Gillis, N., Glineur, F.: Low-rank matrix approximation with weights or missing data is NP-hard. SIAM Journal of Matrix Analysis and Applications\u00a032, 1149\u20131165 (2011)","journal-title":"SIAM Journal of Matrix Analysis and Applications"},{"key":"26_CR10","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1057\/palgrave.jors.2600392","volume":"48","author":"F. Glover","year":"1997","unstructured":"Glover, F., Punnen, A.P.: The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms. Journal of the Operational Research Society\u00a048, 502\u2013510 (1997)","journal-title":"Journal of the Operational Research Society"},{"key":"26_CR11","unstructured":"Glover, F., Ye, T., Punnen, A.P., Kochenberger, G.A.: Private communication"},{"key":"26_CR12","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0167-6377(92)90049-9","volume":"12","author":"L.K. Grover","year":"1992","unstructured":"Grover, L.K.: Local search and the local structure of NP-complete problems. Operations Research Letters\u00a012, 235\u2013243 (1992)","journal-title":"Operations Research Letters"},{"key":"26_CR13","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1016\/S0166-218X(03)00359-7","volume":"129","author":"G. Gutin","year":"2003","unstructured":"Gutin, G., Vainshtein, A., Yeo, A.: Domination analysis of combinatorial optimization problems. Discrete Applied Mathematics\u00a0129, 513\u2013520 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"26_CR14","doi-asserted-by":"publisher","first-page":"2613","DOI":"10.1016\/j.dam.2006.02.010","volume":"154","author":"G. Gutin","year":"2006","unstructured":"Gutin, G., Jensen, T., Yeo, Y.: Domination analysis for multiprocessor scheduling. Discrete Applied Mathematics\u00a0154, 2613\u20132619 (2006)","journal-title":"Discrete Applied Mathematics"},{"key":"26_CR15","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0166-218X(01)00267-0","volume":"119","author":"G. Gutin","year":"2002","unstructured":"Gutin, G., Yeo, A.: Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number. Discrete Applied Mathematics\u00a0119, 107\u2013116 (2002)","journal-title":"Discrete Applied Mathematics"},{"key":"26_CR16","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0167-6377(01)00053-0","volume":"28","author":"G. Gutin","year":"2001","unstructured":"Gutin, G., Yeo, A.: TSP tour domination and Hamilton cycle decomposition of regular graphs. Operations Research Letters\u00a028, 107\u2013111 (2001)","journal-title":"Operations Research Letters"},{"key":"26_CR17","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1006\/jagm.2001.1187","volume":"41","author":"R. Hassin","year":"2001","unstructured":"Hassin, R., Khuller, S.: z-Approximations. Journal of Algorithms\u00a041, 429\u2013442 (2001)","journal-title":"Journal of Algorithms"},{"key":"26_CR18","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.aim.2013.01.005","volume":"237","author":"D. K\u00fchn","year":"2013","unstructured":"K\u00fchn, D., Osthus, D.: Hamilton decompositions of regular expanders: a proof of kelly\u2019s conjecture for large tournaments. Advances in Mathematics\u00a0237, 62\u2013146 (2013)","journal-title":"Advances in Mathematics"},{"key":"26_CR19","unstructured":"Karapetyan, D., Punnen, A.P.: Heuristic algorithms for the bipartite unconstrained 0-1 quadratic programming problem (2012), \n                  \n                    http:\/\/arxiv.org\/abs\/1210.3684"},{"key":"26_CR20","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/j.disc.2003.05.008","volume":"275","author":"A.E. Koller","year":"2004","unstructured":"Koller, A.E., Noble, S.D.: Domination analysis of greedy heuristics for the frequency assignment problem. Discrete Mathematics\u00a0275, 331\u2013338 (2004)","journal-title":"Discrete Mathematics"},{"key":"26_CR21","doi-asserted-by":"crossref","unstructured":"Lu, H., Vaidya, J., Atluri, V., Shin, H., Jiang, L.: Weighted rank-one binary matrix factorization. In: Proceedings of the Eleventh Siam International Conference on Data Mining, pp. 283\u2013294 (2011)","DOI":"10.1137\/1.9781611972818.25"},{"key":"26_CR22","first-page":"26","volume":"16","author":"T.R. Minina","year":"1975","unstructured":"Minina, T.R., Perekrest, V.T.: On a method of approximating solutions of the travelling salesman problem. Soviet Math. Doklady\u00a016, 26\u201330 (1975)","journal-title":"Soviet Math. Doklady"},{"key":"26_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/978-3-642-03367-4_45","volume-title":"Algorithms and Data Structures","author":"J.B. Orlin","year":"2009","unstructured":"Orlin, J.B., Punnen, A.P., Schulz, A.S.: Integer programming: Optimization and evaluation are equivalent. In: Dehne, F., Gavrilova, M., Sack, J.-R., T\u00f3th, C.D. (eds.) WADS 2009. LNCS, vol.\u00a05664, pp. 519\u2013529. Springer, Heidelberg (2009)"},{"key":"26_CR24","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/S0166-218X(01)00268-2","volume":"119","author":"A.P. Punnen","year":"2002","unstructured":"Punnen, A.P., Kabadi, S.: Domination analysis of some heuristics for the asymmetric traveling salesman problem. Discrete Applied Mathematics\u00a0119, 117\u2013128 (2002)","journal-title":"Discrete Applied Mathematics"},{"key":"26_CR25","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s00453-002-0986-1","volume":"35","author":"A.P. Punnen","year":"2003","unstructured":"Punnen, A.P., Margot, F., Kabadi, S.N.: TSP heuristics: domination analysis and complexity. Algorithmica\u00a035, 111\u2013127 (2003)","journal-title":"Algorithmica"},{"key":"26_CR26","unstructured":"Punnen, A.P., Sripratak, P., Karapetyan, D.: The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases (2012), \n                  \n                    http:\/\/arxiv.org\/abs\/1212.3736"},{"key":"26_CR27","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D.: Towards computing the Grothendieck constant. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 525\u2013534 (2009)","DOI":"10.1137\/1.9781611973068.58"},{"key":"26_CR28","first-page":"18","volume":"4","author":"V.I. Rublineckii","year":"1973","unstructured":"Rublineckii, V.I.: Estimates of the accuracy of procedures in the traveling salesman problem. Numerical Mathematics and Computer Technology\u00a04, 18\u201323 (1973) (in Russian)","journal-title":"Numerical Mathematics and Computer Technology"},{"key":"26_CR29","first-page":"8","volume":"31","author":"V. Sarvanov","year":"1981","unstructured":"Sarvanov, V., Doroshko, N.: The approximate solution of the traveling salesman problem by a local algorithm that searches neighborhoods of exponential cardinality in quadratic time. Software: Algorithms and Programs\u00a031, 8\u201311 (1981)","journal-title":"Software: Algorithms and Programs"},{"key":"26_CR30","first-page":"11","volume":"31","author":"V. Sarvanov","year":"1981","unstructured":"Sarvanov, V., Doroshko, N.: The approximate solution of the traveling salesman problem by a local algorithm that searches neighborhoods of factorial cardinality in cubic time. Software: Algorithms and Programs\u00a031, 11\u201313 (1981)","journal-title":"Software: Algorithms and Programs"},{"key":"26_CR31","first-page":"51","volume":"139","author":"V.I. Sarvanov","year":"1978","unstructured":"Sarvanov, V.I.: The mean value of the functional in sampling problems. Vestsi Akademii Navuk BSSR. Seryya Fizika-Matematychnykh Navuk\u00a0139, 51\u201354 (1978)","journal-title":"Vestsi Akademii Navuk BSSR. Seryya Fizika-Matematychnykh Navuk"},{"key":"26_CR32","doi-asserted-by":"crossref","unstructured":"Shen, B.-H., Ji, S., Ye, J.: Mining discrete patterns via binary matrix factorization. In: Proc. of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 757\u2013766. ACM (2009)","DOI":"10.1145\/1557019.1557103"},{"key":"26_CR33","unstructured":"Sripratak, P., Punnen, A.P.: The bipartite boolean quadric polytope: facets and valid inequalities. Working paper, Department of Matheamtics. Simon Fraser university Surrey (2013)"},{"key":"26_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/978-3-540-79228-4_25","volume-title":"Theory and Applications of Models of Computation","author":"J. Tan","year":"2008","unstructured":"Tan, J.: Inapproximability of maximum weighted edge biclique and its applications. In: Agrawal, M., Du, D.-Z., Duan, Z., Li, A. (eds.) TAMC 2008. LNCS, vol.\u00a04978, pp. 282\u2013293. Springer, Heidelberg (2008)"},{"issue":"suppl. 1","key":"26_CR35","doi-asserted-by":"crossref","first-page":"S136","DOI":"10.1093\/bioinformatics\/18.suppl_1.S136","volume":"18","author":"A. Tanay","year":"2002","unstructured":"Tanay, A., Sharan, R., Shamir, R.: Discovering statistically significant biclusters in gene expression data. Bioinformatics\u00a018(suppl. 1), S136\u2013S144 (2002)","journal-title":"Bioinformatics"},{"key":"26_CR36","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1016\/j.disopt.2007.11.009","volume":"5","author":"Y. Twitto","year":"2008","unstructured":"Twitto, Y.: Dominance guarantees for above-average solutions. Discrete Optimization\u00a05, 563\u2013568 (2008)","journal-title":"Discrete Optimization"},{"key":"26_CR37","unstructured":"Vazirani, V.: Approximation Algorithms. Springer (2001)"},{"key":"26_CR38","unstructured":"Vizing, V.G.: Values of the target functional in a priority problem that are majorized by the mean value. Kibernetika, 76\u201378 (1973)"},{"key":"26_CR39","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1016\/j.ejor.2012.07.012","volume":"223","author":"Y. Wang","year":"2012","unstructured":"Wang, Y., Lu, Z., Glover, F., Hao, J.-K.: Path relinking for unconstrained binary quadratic programming. European Journal of Operational Research\u00a0223, 595\u2013604 (2012)","journal-title":"European Journal of Operational Research"},{"key":"26_CR40","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1287\/moor.6.3.319","volume":"6","author":"E. Zemel","year":"1981","unstructured":"Zemel, E.: Measuring the quality of approximate solutions to zero-one programming problems. Mathematics of Operations Research\u00a06, 319\u2013332 (1981)","journal-title":"Mathematics of Operations Research"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40164-0_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T21:37:07Z","timestamp":1557956227000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40164-0_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642401633","9783642401640"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40164-0_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}