TY - JOUR AU - Chen, Peilin AU - Wan, Hai AU - Cai, Shaowei AU - Li, Jia AU - Chen, Haicheng PY - 2020/04/03 Y2 - 2024/03/28 TI - Local Search with Dynamic-Threshold Configuration Checking and Incremental Neighborhood Updating for Maximum k-plex Problem JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 34 IS - 03 SE - AAAI Technical Track: Heuristic Search and Optimization DO - 10.1609/aaai.v34i03.5613 UR - https://ojs.aaai.org/index.php/AAAI/article/view/5613 SP - 2343-2350 AB - <p>The Maximum k-plex Problem is an important combinatorial optimization problem with increasingly wide applications. In this paper, we propose a novel strategy, named Dynamic-threshold Configuration Checking (DCC), to reduce the cycling problem of local search. Due to the complicated neighborhood relations, all the previous local search algorithms for this problem spend a large amount of time in identifying feasible neighbors in each step. To further improve the performance on dense and challenging instances, we propose Double-attributes Incremental Neighborhood Updating (DINU) scheme which reduces the worst-case time complexity per iteration from <em>O</em>(|<em>V</em>|⋅Δ<sub><em>G</em></sub>) to <em>O</em>(<em>k</em> · Δ<sub>‾<em>G</em></sub>). Based on DCC strategy and DINU scheme, we develop a local search algorithm named DCCplex. According to the experiment result, DCCplex shows promising result on DIMACS and BHOSLIB benchmark as well as real-world massive graphs. Especially, DCCplex updates the lower bound of the maximum <em>k</em>-plex for most dense and challenging instances.</p> ER -