Một phương pháp tìm kiếm địa phương mới cho bài toán bao phủ tập hợp đồng nhất sử dụng chiến lược kiểm tra cấu hình hyperedge và sự đa dạng trọng số

Karp R M. Reducibility among combinatorial problems. In: Complexity of Computer Computations. New York: Plenum Press, 1972. 85–103 Chakrabarty K. Test scheduling for core-based systems using mixed-integer linear programming. IEEE Trans Comput- Aided Des Integr Circuits Syst, 2000, 19: 1163–1174 van Bevern R. Towards optimal and expressive kernelization for d-Hitting Set. Comput Comb, 2012, 7434: 121–132 Ausiello G, D’Atri A, Protasi M. Structure preserving reductions among convex optimization problems. J Comput Syst Sci, 1980, 21: 136–153 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–716 Dinur I, Safra S. On the hardness of approximating minimum vertex cover. Ann Math, 2005, 162: 439–485 Caprara A, Fischetti M, Toth P. A heuristic method for the set covering problem. Oper Res, 1999, 47: 730–743 Reiter R. A theory of diagnosis from first principles. Artif Intell, 1987, 32: 57–95 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–166 Angel E, Bampis E, Gourvès L. On the minimum hitting set of bundles problem. Theor Comput Sci, 2009, 410: 4534–4542 Sellis T K. Multiple-query optimization. ACM Trans Database Syst, 1988, 13: 23–52 Avella P, Boccia M, Vasilyev I. Computational experience with general cutting planes for the Set Covering problem. Oper Res Lett, 2009, 37: 16–20 Björklund P, Värbrand P, Yuan D. A column generation method for spatial TDMA scheduling in ad hoc networks. Ad Hoc Netw, 2004, 2: 405–418 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–1226 Caprara A, Toth P, Fischetti M. Algorithms for the set covering problem. Ann Oper Res, 2000, 98: 353–371 Pereira J, Averbakh I. The robust set covering problem with interval data. Ann Oper Res, 2013, 207: 217–235 Yelbay S B, Birbil I, Bülbül K. The set covering problem revisited: an empirical study of the value of dual information. J Ind Manag Optimiz, 2015, 11: 575–594 Galinier P, Hertz A. Solution techniques for the large set covering problem. Discret Appl Mathematics, 2007, 155: 312–326 Yagiura M, Kishida M, Ibaraki T. A 3-flip neighborhood local search for the set covering problem. Eur J Oper Res, 2006, 172: 472–499 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–172 Caserta M. Tabu search-based metaheuristic algorithm for large-scale set covering problems. Metaheuristics Progress Complex Syst Opt, 2007, 39: 43–63 Umetani S, Yagiura M. Relaxation heuristics for the set covering problem. J Oper Res Soc Jpn, 2007, 50: 350–375 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–1403 Bautista J, Pereira J. A GRASP algorithm to solve the unicost set covering problem. Comput Oper Res, 2007, 34: 3162–3173 Ablanedo-Rosas J H, Rego C. Surrogate constraint normalization for the set covering problem. Eur J Oper Res, 2010, 205: 540–551 Sundar S, Singh A. A hybrid heuristic for the set covering problem. Oper Res, 2012, 12: 345–365 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 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–274 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–784 Beasley J E, Chu P C. A genetic algorithm for the set covering problem. Eur J Oper Res, 1996, 94: 392–404 Naji-Azimi Z, Toth P, Galli L. An electromagnetism metaheuristic for the unicost set covering problem. Eur J Oper Res, 2010, 205: 290–300 Glover F. Tabu search-part I. ORSA J Comput, 1989, 1: 190–206 Selman B, Kautz H A, Cohen B. Noise strategies for improving local search. In: Proceedings of National Conference on Artificial Intelligence, Seattle, 1994. 337–343 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–495 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–66 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ébec, 2014. 2703–2709 Cai S W, Su K L. Local search for boolean satisfiability with configuration checking and subscore. Artif Intell, 2013, 204: 75–98 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–1027 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–1843 Beasley J E. OR-Library: distributing test problems by electronic mail. J Oper Res Soc, 1990, 41: 1069–1072 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–342 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–446 Li C M, Huang W Q. Diversification and determinism in local search for satisfiability. Lect Notes Comput Sci, 2005, 3569: 158–172 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–33 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–1696 Xu K, Li W. Many hard examples in exact phase transitions. Theor Comput Sci, 2006, 355: 291–302 Xu K, Li W. Exact phase transitions in random constraint satisfaction problems. J Artif Intell Res, 2000, 12: 93–103 Xu K, Boussemart F, Hemery F, et al. Random constraint satisfaction: easy generation of hard (satisfiable) instances. Artif Intell, 2007, 171: 514–534 Gao J, Wang J N, Yin M H. Experimental analyses on phase transitions in compiling satisfiability problems. Sci China Inf Sci, 2015, 58: 032104 Huang P, Yin M H. An upper (lower) bound for Max (Min) CSP. Sci China Inf Sci, 2014, 57: 072109 Grossman T, Wool A. Computational experience with approximation algorithms for the set covering problem. Eur J Oper Res, 1997, 101: 81–92