{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T09:24:14Z","timestamp":1774257854164,"version":"3.50.1"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2017,2,9]],"date-time":"2017-02-09T00:00:00Z","timestamp":1486598400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Sci. China Inf. Sci."],"published-print":{"date-parts":[[2017,6]]},"DOI":"10.1007\/s11432-015-5377-8","type":"journal-article","created":{"date-parts":[[2017,2,13]],"date-time":"2017-02-13T05:32:49Z","timestamp":1486963969000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":38,"title":["A novel local search for unicost set covering problem using hyperedge configuration checking and weight diversity","\u57fa\u4e8e\u8d85\u8fb9\u914d\u7f6e\u68c0\u6d4b\u548c\u6743\u503c\u591a\u6837\u5316\u7b56\u7565\u7684\u5c40\u90e8\u641c\u7d22\u6539\u8fdb\u7b97\u6cd5\u6c42\u89e3\u96c6\u5408\u8986\u76d6\u95ee\u9898"],"prefix":"10.1007","volume":"60","author":[{"given":"Yiyuan","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dantong","family":"Ouyang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liming","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minghao","family":"Yin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,2,9]]},"reference":[{"key":"5377_CR1","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R M Karp","year":"1972","unstructured":"Karp R M. Reducibility among combinatorial problems. In: Complexity of Computer Computations. New York: Plenum Press, 1972. 85\u2013103"},{"key":"5377_CR2","doi-asserted-by":"crossref","first-page":"1163","DOI":"10.1109\/43.875306","volume":"19","author":"K Chakrabarty","year":"2000","unstructured":"Chakrabarty K. Test scheduling for core-based systems using mixed-integer linear programming. IEEE Trans Comput- Aided Des Integr Circuits Syst, 2000, 19: 1163\u20131174","journal-title":"IEEE Trans Comput- Aided Des Integr Circuits Syst"},{"key":"5377_CR3","first-page":"121","volume":"7434","author":"R Bevern van","year":"2012","unstructured":"van Bevern R. Towards optimal and expressive kernelization for d-Hitting Set. Comput Comb, 2012, 7434: 121\u2013132","journal-title":"Comput Comb"},{"key":"5377_CR4","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/0022-0000(80)90046-X","volume":"21","author":"G Ausiello","year":"1980","unstructured":"Ausiello G, D\u2019Atri A, Protasi M. Structure preserving reductions among convex optimization problems. J Comput Syst Sci, 1980, 21: 136\u2013153","journal-title":"J Comput Syst Sci"},{"key":"5377_CR5","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1613\/jair.3907","volume":"46","author":"S W Cai","year":"2014","unstructured":"Cai S W, Su K L, Luo C, et al. NuMVC: An efficient local search algorithm for minimum vertex cover. J Artif Intell Res, 2014, 46: 687\u2013716","journal-title":"J Artif Intell Res"},{"key":"5377_CR6","doi-asserted-by":"crossref","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur I, Safra S. On the hardness of approximating minimum vertex cover. Ann Math, 2005, 162: 439\u2013485","journal-title":"Ann Math"},{"key":"5377_CR7","doi-asserted-by":"crossref","first-page":"730","DOI":"10.1287\/opre.47.5.730","volume":"47","author":"A Caprara","year":"1999","unstructured":"Caprara A, Fischetti M, Toth P. A heuristic method for the set covering problem. Oper Res, 1999, 47: 730\u2013743","journal-title":"Oper Res"},{"key":"5377_CR8","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0004-3702(87)90062-2","volume":"32","author":"R Reiter","year":"1987","unstructured":"Reiter R. A theory of diagnosis from first principles. Artif Intell, 1987, 32: 57\u201395","journal-title":"Artif Intell"},{"key":"5377_CR9","first-page":"157","volume-title":"Proceedings of the Intelligent Computing 3rd International Conference on Advanced Intelligent Computing Theories and Applications. Berlin: Springer","author":"X F Zhao","year":"2007","unstructured":"Zhao X F, Ouyang D T. Improved algorithms for deriving all minimal conflict sets in model-based diagnosis. In: Proceedings of the Intelligent Computing 3rd International Conference on Advanced Intelligent Computing Theories and Applications. Berlin: Springer, 2007. 157\u2013166"},{"key":"5377_CR10","doi-asserted-by":"crossref","first-page":"4534","DOI":"10.1016\/j.tcs.2009.08.017","volume":"410","author":"E Angel","year":"2009","unstructured":"Angel E, Bampis E, Gourv\u00e8s L. On the minimum hitting set of bundles problem. Theor Comput Sci, 2009, 410: 4534\u20134542","journal-title":"Theor Comput Sci"},{"key":"5377_CR11","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/42201.42203","volume":"13","author":"T K Sellis","year":"1988","unstructured":"Sellis T K. Multiple-query optimization. ACM Trans Database Syst, 1988, 13: 23\u201352","journal-title":"ACM Trans Database Syst"},{"key":"5377_CR12","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.orl.2008.09.009","volume":"37","author":"P Avella","year":"2009","unstructured":"Avella P, Boccia M, Vasilyev I. Computational experience with general cutting planes for the Set Covering problem. Oper Res Lett, 2009, 37: 16\u201320","journal-title":"Oper Res Lett"},{"key":"5377_CR13","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/j.adhoc.2003.09.002","volume":"2","author":"P Bj\u00f6rklund","year":"2004","unstructured":"Bj\u00f6rklund P, V\u00e4rbrand P, Yuan D. A column generation method for spatial TDMA scheduling in ad hoc networks. Ad Hoc Netw, 2004, 2: 405\u2013418","journal-title":"Ad Hoc Netw"},{"key":"5377_CR14","doi-asserted-by":"crossref","first-page":"1204","DOI":"10.1016\/j.cor.2006.07.012","volume":"35","author":"T D Hemazro","year":"2008","unstructured":"Hemazro T D, Jaumard B, Marcotte O. A column generation and branch-and-cut algorithm for the channel assignment problem. Comput Oper Res, 2008, 35: 1204\u20131226","journal-title":"Comput Oper Res"},{"key":"5377_CR15","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1023\/A:1019225027893","volume":"98","author":"A Caprara","year":"2000","unstructured":"Caprara A, Toth P, Fischetti M. Algorithms for the set covering problem. Ann Oper Res, 2000, 98: 353\u2013371","journal-title":"Ann Oper Res"},{"key":"5377_CR16","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/s10479-011-0876-5","volume":"207","author":"J Pereira","year":"2013","unstructured":"Pereira J, Averbakh I. The robust set covering problem with interval data. Ann Oper Res, 2013, 207: 217\u2013235","journal-title":"Ann Oper Res"},{"key":"5377_CR17","doi-asserted-by":"crossref","first-page":"575","DOI":"10.3934\/jimo.2015.11.575","volume":"11","author":"S B Yelbay","year":"2015","unstructured":"Yelbay S B, Birbil I, B\u00fclb\u00fcl K. The set covering problem revisited: an empirical study of the value of dual information. J Ind Manag Optimiz, 2015, 11: 575\u2013594","journal-title":"J Ind Manag Optimiz"},{"key":"5377_CR18","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1016\/j.dam.2006.04.043","volume":"155","author":"P Galinier","year":"2007","unstructured":"Galinier P, Hertz A. Solution techniques for the large set covering problem. Discret Appl Mathematics, 2007, 155: 312\u2013326","journal-title":"Discret Appl Mathematics"},{"key":"5377_CR19","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1016\/j.ejor.2004.10.018","volume":"172","author":"M Yagiura","year":"2006","unstructured":"Yagiura M, Kishida M, Ibaraki T. A 3-flip neighborhood local search for the set covering problem. Eur J Oper Res, 2006, 172: 472\u2013499","journal-title":"Eur J Oper Res"},{"key":"5377_CR20","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1504\/IJOR.2007.012458","volume":"2","author":"G W Kinney","year":"2007","unstructured":"Kinney G W, Barnes J W, Colletti B W. A reactive tabu search algorithm with variable clustering for the unicost set covering problem. Int J Oper Res, 2007, 2: 156\u2013172","journal-title":"Int J Oper Res"},{"key":"5377_CR21","first-page":"43","volume":"39","author":"M Caserta","year":"2007","unstructured":"Caserta M. Tabu search-based metaheuristic algorithm for large-scale set covering problems. Metaheuristics Progress Complex Syst Opt, 2007, 39: 43\u201363","journal-title":"Metaheuristics Progress Complex Syst Opt"},{"key":"5377_CR22","doi-asserted-by":"crossref","first-page":"350","DOI":"10.15807\/jorsj.50.350","volume":"50","author":"S Umetani","year":"2007","unstructured":"Umetani S, Yagiura M. Relaxation heuristics for the set covering problem. J Oper Res Soc Jpn, 2007, 50: 350\u2013375","journal-title":"J Oper Res Soc Jpn"},{"key":"5377_CR23","doi-asserted-by":"crossref","first-page":"1387","DOI":"10.1016\/j.ejor.2005.09.028","volume":"176","author":"G Lan","year":"2007","unstructured":"Lan G, De Puy G W, Whitehouse G E. An effective and simple heuristic for the set covering problem. Eur J Oper Res, 2007, 176: 1387\u20131403","journal-title":"Eur J Oper Res"},{"key":"5377_CR24","doi-asserted-by":"crossref","first-page":"3162","DOI":"10.1016\/j.cor.2005.11.026","volume":"34","author":"J Bautista","year":"2007","unstructured":"Bautista J, Pereira J. A GRASP algorithm to solve the unicost set covering problem. Comput Oper Res, 2007, 34: 3162\u20133173","journal-title":"Comput Oper Res"},{"key":"5377_CR25","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1016\/j.ejor.2010.02.008","volume":"205","author":"J H Ablanedo-Rosas","year":"2010","unstructured":"Ablanedo-Rosas J H, Rego C. Surrogate constraint normalization for the set covering problem. Eur J Oper Res, 2010, 205: 540\u2013551","journal-title":"Eur J Oper Res"},{"key":"5377_CR26","first-page":"345","volume":"12","author":"S Sundar","year":"2012","unstructured":"Sundar S, Singh A. A hybrid heuristic for the set covering problem. Oper Res, 2012, 12: 345\u2013365","journal-title":"Oper Res"},{"key":"5377_CR27","doi-asserted-by":"crossref","first-page":"189164","DOI":"10.1155\/2014\/189164","volume":"2014","author":"B Crawford","year":"2014","unstructured":"Crawford B, Soto R, Cuesta R, et al. Application of the artificial bee colony algorithm for solving the set covering problem. Sci World J, 2014, 2014: 189164","journal-title":"Sci World J"},{"key":"5377_CR28","first-page":"265","volume-title":"Proceedings of the IEEE International Conference of the Chilean Computer Science Society, Curico","author":"M H Mulati","year":"2011","unstructured":"Mulati M H, Constantino A A. Ant-Line: a line-oriented ACO algorithm for the set covering problem. In: Proceedings of the IEEE International Conference of the Chilean Computer Science Society, Curico, 2011. 265\u2013274"},{"key":"5377_CR29","doi-asserted-by":"crossref","first-page":"774","DOI":"10.1016\/j.cie.2010.02.011","volume":"58","author":"Z G Ren","year":"2010","unstructured":"Ren Z G, Feng Z R, Ke L J, et al. New ideas for applying ant colony optimization to the set covering problem. Comput Ind Eng, 2010, 58: 774\u2013784","journal-title":"Comput Ind Eng"},{"key":"5377_CR30","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1016\/0377-2217(95)00159-X","volume":"94","author":"J E Beasley","year":"1996","unstructured":"Beasley J E, Chu P C. A genetic algorithm for the set covering problem. Eur J Oper Res, 1996, 94: 392\u2013404","journal-title":"Eur J Oper Res"},{"key":"5377_CR31","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1016\/j.ejor.2010.01.035","volume":"205","author":"Z Naji-Azimi","year":"2010","unstructured":"Naji-Azimi Z, Toth P, Galli L. An electromagnetism metaheuristic for the unicost set covering problem. Eur J Oper Res, 2010, 205: 290\u2013300","journal-title":"Eur J Oper Res"},{"key":"5377_CR32","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","volume":"1","author":"F Glover","year":"1989","unstructured":"Glover F. Tabu search-part I. ORSA J Comput, 1989, 1: 190\u2013206","journal-title":"ORSA J Comput"},{"key":"5377_CR33","first-page":"337","volume-title":"Proceedings of National Conference on Artificial Intelligence, Seattle","author":"B Selman","year":"1994","unstructured":"Selman B, Kautz H A, Cohen B. Noise strategies for improving local search. In: Proceedings of National Conference on Artificial Intelligence, Seattle, 1994. 337\u2013343"},{"key":"5377_CR34","first-page":"489","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence, Beijing","author":"S W Cai","year":"2013","unstructured":"Cai S W, Su K L. Comprehensive score: towards efficient local search for sat with long clauses. In: Proceedings of the International Joint Conference on Artificial Intelligence, Beijing, 2013. 489\u2013495"},{"key":"5377_CR35","first-page":"59","volume-title":"Proceedings of the IEEE International Conference on Tools with Artificial Intelligence, Boca Raton","author":"S W Cai","year":"2011","unstructured":"Cai S W, Su K L. Local search with configuration checking for SAT. In: Proceedings of the IEEE International Conference on Tools with Artificial Intelligence, Boca Raton, 2011. 59\u201366"},{"key":"5377_CR36","first-page":"2703","volume-title":"Proceedings of National Conference on Artificial Intelligence, Qu\u00e9bec","author":"C Luo","year":"2014","unstructured":"Luo C, Cai SW, Wu W, et al. Double configuration checking in stochastic local search for satisfiability. In: Proceedings of National Conference on Artificial Intelligence, Qu\u00e9bec, 2014. 2703\u20132709"},{"key":"5377_CR37","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.artint.2013.09.001","volume":"204","author":"S W Cai","year":"2013","unstructured":"Cai S W, Su K L. Local search for boolean satisfiability with configuration checking and subscore. Artif Intell, 2013, 204: 75\u201398","journal-title":"Artif Intell"},{"key":"5377_CR38","first-page":"1014","volume":"45","author":"C Luo","year":"2014","unstructured":"Luo C, Cai S W, Su K L, et al. Clause states based configuration checking in local search for satisfiability. IEEE Trans cybern, 2014, 45: 1014\u20131027","journal-title":"IEEE Trans cybern"},{"key":"5377_CR39","doi-asserted-by":"crossref","first-page":"1830","DOI":"10.1109\/TC.2014.2346196","volume":"64","author":"C Luo","year":"2015","unstructured":"Luo C, Cai S W, Wu W, et al. CCLS: an efficient local search algorithm for weighted maximum satisfiability. IEEE Trans Comput, 2015, 64: 1830\u20131843","journal-title":"IEEE Trans Comput"},{"key":"5377_CR40","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1057\/jors.1990.166","volume":"41","author":"J E Beasley","year":"1990","unstructured":"Beasley J E. OR-Library: distributing test problems by electronic mail. J Oper Res Soc, 1990, 41: 1069\u20131072","journal-title":"J Oper Res Soc"},{"key":"5377_CR41","first-page":"337","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence, Edinburgh","author":"K Xu","year":"2005","unstructured":"Xu K, Boussemart F, Hemery F, et al. A simple model to generate hard satisfiable instances. In: Proceedings of the International Joint Conference on Artificial Intelligence, Edinburgh, 2005. 337\u2013342"},{"key":"5377_CR42","first-page":"440","volume-title":"Proceedings of National Conference on Artificial Intelligence, San Jose","author":"B Selman","year":"1992","unstructured":"Selman B, Levesque H J, Mitchell D G. A new method for solving hard satisfiability problems. In: Proceedings of National Conference on Artificial Intelligence, San Jose, 1992. 440\u2013446"},{"key":"5377_CR43","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1007\/11499107_12","volume":"3569","author":"C M Li","year":"2005","unstructured":"Li C M, Huang W Q. Diversification and determinism in local search for satisfiability. Lect Notes Comput Sci, 2005, 3569: 158\u2013172","journal-title":"Lect Notes Comput Sci"},{"key":"5377_CR44","first-page":"28","volume-title":"Proceedings of National Conference on Artificial Intelligence, Washington","author":"I P Gent","year":"1993","unstructured":"Gent I P, Walsh T. Towards an understanding of hill-climbing procedures for SAT. In: Proceedings of National Conference on Artificial Intelligence, Washington, 1993. 28\u201333"},{"key":"5377_CR45","doi-asserted-by":"crossref","first-page":"1672","DOI":"10.1016\/j.artint.2011.03.003","volume":"175","author":"S W Cai","year":"2011","unstructured":"Cai S W, Su K L, Sattar A. Local search with edge weighting and configuration checking heuristics for minimum vertex cover. Artif Intell, 2011, 175: 1672\u20131696","journal-title":"Artif Intell"},{"key":"5377_CR46","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/j.tcs.2006.01.001","volume":"355","author":"K Xu","year":"2006","unstructured":"Xu K, Li W. Many hard examples in exact phase transitions. Theor Comput Sci, 2006, 355: 291\u2013302","journal-title":"Theor Comput Sci"},{"key":"5377_CR47","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1613\/jair.696","volume":"12","author":"K Xu","year":"2000","unstructured":"Xu K, Li W. Exact phase transitions in random constraint satisfaction problems. J Artif Intell Res, 2000, 12: 93\u2013103","journal-title":"J Artif Intell Res"},{"key":"5377_CR48","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1016\/j.artint.2007.04.001","volume":"171","author":"K Xu","year":"2007","unstructured":"Xu K, Boussemart F, Hemery F, et al. Random constraint satisfaction: easy generation of hard (satisfiable) instances. Artif Intell, 2007, 171: 514\u2013534","journal-title":"Artif Intell"},{"key":"5377_CR49","first-page":"032104","volume":"58","author":"J Gao","year":"2015","unstructured":"Gao J, Wang J N, Yin M H. Experimental analyses on phase transitions in compiling satisfiability problems. Sci China Inf Sci, 2015, 58: 032104","journal-title":"Sci China Inf Sci"},{"key":"5377_CR50","first-page":"072109","volume":"57","author":"P Huang","year":"2014","unstructured":"Huang P, Yin M H. An upper (lower) bound for Max (Min) CSP. Sci China Inf Sci, 2014, 57: 072109","journal-title":"Sci China Inf Sci"},{"key":"5377_CR51","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/S0377-2217(96)00161-0","volume":"101","author":"T Grossman","year":"1997","unstructured":"Grossman T, Wool A. Computational experience with approximation algorithms for the set covering problem. Eur J Oper Res, 1997, 101: 81\u201392","journal-title":"Eur J Oper Res"}],"container-title":["Science China Information Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-015-5377-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11432-015-5377-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-015-5377-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T15:58:58Z","timestamp":1568822338000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11432-015-5377-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,9]]},"references-count":51,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["5377"],"URL":"https:\/\/doi.org\/10.1007\/s11432-015-5377-8","relation":{},"ISSN":["1674-733X","1869-1919"],"issn-type":[{"value":"1674-733X","type":"print"},{"value":"1869-1919","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,2,9]]},"article-number":"062103"}}