Research map / Learning theory and algorithms / Combinatorial and search optimization
Local Search with Dynamic-Threshold Configuration Checking and Incremental Neighborhood Updating for Maximum k-plex Problem
Peilin Chen, Hai Wan, Shaowei Cai, Jia Li, Haicheng Chen
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace SCC with Dynamic-threshold Configuration Checking (ablation) | DCCplex · BHOSLIB k=4 | instances with better max(avg) result: 7(21) vs 0(0) | Improved |
| replace SCC with DCC (ablation) | DCCplex · DIMACS k=2 | instances with better max(avg) result: 3(10) vs 1(1) | Improved |
| replace SCC with DCC (ablation) | DCCplex · Massive graphs k=3 | instances with better max(avg) result: 0(1) vs 0(3) | No clear effect |
| add DINU incremental neighborhood updating (ablation) | DCCplex · DIMACS/BHOSLIB (60 instances) | search steps per 1000s (speedup ratio): speedup 230 on MANN a81 | Improved |
| DCCplex vs FD-TS | local search for max k-plex · frb100-40 k=4 | best k-plex size: 170 -> 178 | Improved |
| DCCplex vs FD-TS | local search for max k-plex · brock/san DIMACS instances | best/average k-plex size: san400 0.7 2 k=2: 33(32.2) -> 32(32) | Mixed |
Closest papers by meaning
- Improving Local Search Algorithms via Probabilistic Configuration Checking (AAAI 2022 · similarity 0.89)
- Two Efficient Local Search Algorithms for Maximum Weight Clique Problem (AAAI 2016 · similarity 0.89)
- Systematic Exploration of Larger Local Search Neighborhoods for the Minimum Vertex Cover Problem (AAAI 2017 · similarity 0.88)
- NukCP: An Improved Local Search Algorithm for Maximum k-Club Problem (AAAI 2022 · similarity 0.88)
- KD-Club: An Efficient Exact Algorithm with New Coloring-Based Upper Bound for the Maximum k-Defective Clique Problem (AAAI 2024 · similarity 0.83)
- A Fast Exact Solver with Theoretical Analysis for the Maximum Edge-Weighted Clique Problem (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
