TY - GEN
T1 - FWLS
T2 - 7th International Frontiers in Algorithmics Workshop and the 9th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2013
AU - Wu, Wei
AU - Luo, Chuan
AU - Su, Kaile
PY - 2013
Y1 - 2013
N2 - Local search (LS) is a widely used, general approach for solving hard combinatorial search problems, such as the graph coloring problem (GCP). One main advantage of this method is that effective heuristics for a problem may lead to improvements in solving other problems. Recently, it has been shown that an initial LS algorithm for the Boolean satisfiability problem (SAT) called WalkSAT is extremely effective for random SAT instances. Thus, it is interesting to apply the heuristics in WalkSAT to GCP. This paper proposes a random walk based heuristic, which is inspired by WalkSAT but differs in the tie-breaking mechanism. This new heuristic leads to a new LS algorithm for GCP namely FWLS. The experiments on the DIMACS benchmark show that FWLS finds optimal (or best known) solutions for most instances. Also, when compared to other GCP algorithms, including a greedy one, an LS one and a hybrid one, FWLS exhibits very competitive or better performance.
AB - Local search (LS) is a widely used, general approach for solving hard combinatorial search problems, such as the graph coloring problem (GCP). One main advantage of this method is that effective heuristics for a problem may lead to improvements in solving other problems. Recently, it has been shown that an initial LS algorithm for the Boolean satisfiability problem (SAT) called WalkSAT is extremely effective for random SAT instances. Thus, it is interesting to apply the heuristics in WalkSAT to GCP. This paper proposes a random walk based heuristic, which is inspired by WalkSAT but differs in the tie-breaking mechanism. This new heuristic leads to a new LS algorithm for GCP namely FWLS. The experiments on the DIMACS benchmark show that FWLS finds optimal (or best known) solutions for most instances. Also, when compared to other GCP algorithms, including a greedy one, an LS one and a hybrid one, FWLS exhibits very competitive or better performance.
UR - https://www.scopus.com/pages/publications/84884846224
U2 - 10.1007/978-3-642-38756-2_11
DO - 10.1007/978-3-642-38756-2_11
M3 - 会议稿件
AN - SCOPUS:84884846224
SN - 9783642387555
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 84
EP - 93
BT - Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Third Joint International Conference, FAW-AAIM 2013, Proceedings
Y2 - 26 June 2013 through 28 June 2013
ER -