Local Search with Dynamic-Threshold Configuration Checking and Incremental Neighborhood Updating for Maximum k-plex Problem

Authors

  • Peilin Chen Sun Yat-sen University
  • Hai Wan Sun Yat-sen University
  • Shaowei Cai Chinese Academy of Sciences
  • Jia Li Sun Yat-sen University
  • Haicheng Chen Sun Yat-sen University

DOI:

https://doi.org/10.1609/aaai.v34i03.5613

Abstract

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 O(|V|⋅ΔG) to O(k · ΔG). 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 k-plex for most dense and challenging instances.

Downloads

Published

2020-04-03

How to Cite

Chen, P., Wan, H., Cai, S., Li, J., & Chen, H. (2020). Local Search with Dynamic-Threshold Configuration Checking and Incremental Neighborhood Updating for Maximum k-plex Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 34(03), 2343-2350. https://doi.org/10.1609/aaai.v34i03.5613

Issue

Section

AAAI Technical Track: Heuristic Search and Optimization