Yi Zhou
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Yi Zhou has a total of 56 co-authors. Here are the top co-authors by number of shared publications:
- Mingyu Xiao
University of Electronic Science and Technology of China, Chengdu, China
8 shared publications Chenghao Zhu
5 shared publications- Jin-Kao Hao
Department of Computer Science, LERIA Laboratory, University of Angers, Angers, France
5 shared publications Haoyu Jiang
4 shared publications- Zhang-Hua Fu
Shenzhen Institute of Artificial Intelligence and Robotics for Society The Chinese University of Hong Kong Shenzhen Shenzhen China
4 shared publications Chunyu Luo
3 shared publications
Latest Publications
- 17 August 2026
- Published by Elsevier in European Journal of Operational Research
Exact clique number manipulation via edge interdiction
- 17 August 2026
- Published by Elsevier in European Journal of Operational Research
Exact clique number manipulation via edge interdiction
- 3 July 2026
- Published by Elsevier in Knowledge-Based Systems
- Vol. 350
A branch-and-bound approach for maximum low-diameter dense subgraph problems
- 3 July 2026
- Published by Elsevier in Knowledge-Based Systems
- Vol. 350
A branch-and-bound approach for maximum low-diameter dense subgraph problems
- 1 July 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
A Reduction-Driven Local Search for the Generalized Independent Set Problem
The Generalized Independent Set (GIS) problem extends the classical maximum independent set problem by incorporating profits for vertices and penalties for edges. This generalized problem has been identified in diverse applications in fields such as forest harvesting, competitive facility location, social network analysis, and even machine learning. However, solving the GIS problem in large-scale, real-world networks remains computationally challenging. In this paper, we explore data reduction techniques to address this challenge. We first propose 14 reduction rules that can reduce the input graph with rigorous optimality guarantees. We then present a reduction-driven local search (RLS) algorithm that integrates these reduction rules into the preprocessing, the initial solution generation, and the local search components in a computationally efficient way. The RLS is empirically evaluated on 278 graphs drawn from different application scenarios. The results indicate that the RLS is highly competitive: for most graphs, it achieves significantly superior solutions compared with other known solvers, and it effectively provides solutions for graphs exceeding 260 million edges, a task at which every other known method fails. Analysis also reveals that data reduction plays a key role in achieving such a competitive performance. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search and Approximation Algorithms. Funding: This research was supported by the National Natural Science Foundation of China [Grants 62372093 and 62372095]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1203 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2025.1203 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
- 1 July 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
A Reduction-Driven Local Search for the Generalized Independent Set Problem
The Generalized Independent Set (GIS) problem extends the classical maximum independent set problem by incorporating profits for vertices and penalties for edges. This generalized problem has been identified in diverse applications in fields such as forest harvesting, competitive facility location, social network analysis, and even machine learning. However, solving the GIS problem in large-scale, real-world networks remains computationally challenging. In this paper, we explore data reduction techniques to address this challenge. We first propose 14 reduction rules that can reduce the input graph with rigorous optimality guarantees. We then present a reduction-driven local search (RLS) algorithm that integrates these reduction rules into the preprocessing, the initial solution generation, and the local search components in a computationally efficient way. The RLS is empirically evaluated on 278 graphs drawn from different application scenarios. The results indicate that the RLS is highly competitive: for most graphs, it achieves significantly superior solutions compared with other known solvers, and it effectively provides solutions for graphs exceeding 260 million edges, a task at which every other known method fails. Analysis also reveals that data reduction plays a key role in achieving such a competitive performance. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search and Approximation Algorithms. Funding: This research was supported by the National Natural Science Foundation of China [Grants 62372093 and 62372095]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1203 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2025.1203 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
- 10 June 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
Code and Data Repository for A Reduction-Driven Local Search for the Generalized Independent Set Problem
The software and data in this repository are a snapshot of the software and data that were used in the research reported on in the paper A Reduction-Driven Local Search for the Generalized Independent Set Problem by Y.P. Liu, Y. Zhou, Z.X. Xu, M.Y. Xiao, and J.K. Hao.
- 10 June 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
Code and Data Repository for A Reduction-Driven Local Search for the Generalized Independent Set Problem
The software and data in this repository are a snapshot of the software and data that were used in the research reported on in the paper A Reduction-Driven Local Search for the Generalized Independent Set Problem by Y.P. Liu, Y. Zhou, Z.X. Xu, M.Y. Xiao, and J.K. Hao.
- Open Access
- 20 February 2026
- Published by Springer Nature in Journal of Heuristics
- Vol. 32 (1) , 9
Graph downsizing: a fast heuristic for querying closely connected subgraphs
The vertex connectivity of a graph is the minimum number of vertices whose removal disconnects the graph, and it is a fundamental notion that measures the level of interconnectedness of vertices. Mining subgraphs with high vertex connectivity has wide applications in robust and efficient communication networks and the organization of task groups. However, existing approaches often neglect size constraints, leading to subgraphs that are either too large or too small for practical use. Therefore, in this paper, we introduce the size constraint and formulate the graph downsizing problem: Given a graph G with n vertices and a positive integer $$\tau <n$$ , find an induced subgraph of size $$n-\tau $$ that maximizes vertex connectivity. We first analyze the computational complexity of the graph downsizing problem and show that the problem is hard in several aspects. To solve the problem in practice, we use a nesting tree structure to represent relations between maximal cohesive subgraphs in G . This structure allows us to develop an efficient heuristic, called inundation downsizing algorithm, to find highly vertex-connected subgraphs of different sizes. Experimental results reveal that our heuristic is able to produce almost optimal solutions on real-world datasets with up to 1 million vertices while incurring small time costs.- 20 February 2026
- Published by Springer Nature in Journal of Heuristics
- Vol. 32 (1) , 9
Open AccessGraph downsizing: a fast heuristic for querying closely connected subgraphs
The vertex connectivity of a graph is the minimum number of vertices whose removal disconnects the graph, and it is a fundamental notion that measures the level of interconnectedness of vertices. Mining subgraphs with high vertex connectivity has wide applications in robust and efficient communication networks and the organization of task groups. However, existing approaches often neglect size constraints, leading to subgraphs that are either too large or too small for practical use. Therefore, in this paper, we introduce the size constraint and formulate the graph downsizing problem: Given a graph G with n vertices and a positive integer $$\tau <n$$ , find an induced subgraph of size $$n-\tau $$ that maximizes vertex connectivity. We first analyze the computational complexity of the graph downsizing problem and show that the problem is hard in several aspects. To solve the problem in practice, we use a nesting tree structure to represent relations between maximal cohesive subgraphs in G . This structure allows us to develop an efficient heuristic, called inundation downsizing algorithm, to find highly vertex-connected subgraphs of different sizes. Experimental results reveal that our heuristic is able to produce almost optimal solutions on real-world datasets with up to 1 million vertices while incurring small time costs. - Open Access
Adaptive Confidence Gating in Multi-Agent Collaboration for Efficient and Optimized Code Generation
While Large Language Models (LLMs) have catalyzed breakthroughs in automated code generation, Small Language Models (SLMs) often encounter reasoning bottlenecks and failure loops when addressing complex logical requirements. To overcome these challenges, we propose DebateCoder, a multi-agent collaborative framework designed to improve the reasoning ability of SLMs (e.g., Pangu-1B) in resource-constrained environments. DebateCoder uses a structured role-playing protocol with three agents: User Agent (A_UA), Technical Agent (A_TA), and Quality Assurance Agent (A_QA). It also includes an Adaptive Confidence Gating mechanism with a 95% threshold to balance accuracy and inference efficiency. In addition, we introduce a multi-turn deliberation module and a reviewer-guided analytical debugging loop for orthogonal pre-generation debate and post-generation refinement. Experiments on HumanEval and MBPP show that DebateCoder achieves 70.12% Pass@1 on HumanEval, outperforming MapCoder while reducing API overhead by about 35%. These results indicate that collaborative protocols can mitigate limitations of small-parameter models and provide a scalable, efficient approach to high-quality automated software engineering.
Open AccessAdaptive Confidence Gating in Multi-Agent Collaboration for Efficient and Optimized Code Generation
While Large Language Models (LLMs) have catalyzed breakthroughs in automated code generation, Small Language Models (SLMs) often encounter reasoning bottlenecks and failure loops when addressing complex logical requirements. To overcome these challenges, we propose DebateCoder, a multi-agent collaborative framework designed to improve the reasoning ability of SLMs (e.g., Pangu-1B) in resource-constrained environments. DebateCoder uses a structured role-playing protocol with three agents: User Agent (A_UA), Technical Agent (A_TA), and Quality Assurance Agent (A_QA). It also includes an Adaptive Confidence Gating mechanism with a 95% threshold to balance accuracy and inference efficiency. In addition, we introduce a multi-turn deliberation module and a reviewer-guided analytical debugging loop for orthogonal pre-generation debate and post-generation refinement. Experiments on HumanEval and MBPP show that DebateCoder achieves 70.12% Pass@1 on HumanEval, outperforming MapCoder while reducing API overhead by about 35%. These results indicate that collaborative protocols can mitigate limitations of small-parameter models and provide a scalable, efficient approach to high-quality automated software engineering.
- Open Access
Exact Clique Number Manipulation via Edge Interdiction
The Edge Interdiction Clique Problem (EICP) aims to remove at most $k$ edges from a graph so as to minimize the size of the largest clique in the remaining graph. This problem captures a fundamental question in graph manipulation: which edges are structurally critical for preserving large cliques? Such a problem is also motivated by practical applications including protein function maintenance and image matching. The EICP is computationally challenging and belongs to a complexity class beyond NP. Existing approaches rely on general mixed-integer bilevel programming solvers or reformulate the problem into a single-level mixed integer linear program. However, they are still not scalable when the graph size and interdiction budget $k$ grow. To overcome this, we investigate new mixed integer linear formulations, which recast the problem into a sequence of parameterized Edge Blocker Clique Problems (EBCP). This perspective decomposes the original problem into simpler subproblems and enables tighter modeling of clique-related inequalities. Furthermore, we propose a two-stage exact algorithm, \textsc{RLCM}, which first applies problem-specific reduction techniques to shrink the graph and then solves the reduced problem using a tailored branch-and-cut framework. Extensive computational experiments on maximum clique benchmark graphs, large real-world sparse networks, and random graphs demonstrate that \textsc{RLCM} consistently outperforms existing approaches.Open AccessExact Clique Number Manipulation via Edge Interdiction
The Edge Interdiction Clique Problem (EICP) aims to remove at most $k$ edges from a graph so as to minimize the size of the largest clique in the remaining graph. This problem captures a fundamental question in graph manipulation: which edges are structurally critical for preserving large cliques? Such a problem is also motivated by practical applications including protein function maintenance and image matching. The EICP is computationally challenging and belongs to a complexity class beyond NP. Existing approaches rely on general mixed-integer bilevel programming solvers or reformulate the problem into a single-level mixed integer linear program. However, they are still not scalable when the graph size and interdiction budget $k$ grow. To overcome this, we investigate new mixed integer linear formulations, which recast the problem into a sequence of parameterized Edge Blocker Clique Problems (EBCP). This perspective decomposes the original problem into simpler subproblems and enables tighter modeling of clique-related inequalities. Furthermore, we propose a two-stage exact algorithm, \textsc{RLCM}, which first applies problem-specific reduction techniques to shrink the graph and then solves the reduced problem using a tailored branch-and-cut framework. Extensive computational experiments on maximum clique benchmark graphs, large real-world sparse networks, and random graphs demonstrate that \textsc{RLCM} consistently outperforms existing approaches. - 27 December 2025
- Published by Elsevier in Computers & Operations Research
- Vol. 188
A near-real-time reduction-based algorithm for coloring massive graphs
- 27 December 2025
- Published by Elsevier in Computers & Operations Research
- Vol. 188
A near-real-time reduction-based algorithm for coloring massive graphs
- 20 November 2025
- Published by Elsevier in European Journal of Operational Research
- Vol. 331 (2) , 396-405
Fast exact algorithms for the maximum diversity problem
- 20 November 2025
- Published by Elsevier in European Journal of Operational Research
- Vol. 331 (2) , 396-405
Fast exact algorithms for the maximum diversity problem
- Open Access
A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems
A graph with $n$ vertices is an $f(\cdot)$-dense graph if it has at least $f(n)$ edges, $f(\cdot)$ being a well-defined function. The notion $f(\cdot)$-dense graph encompasses various clique models like $γ$-quasi cliques, $k$-defective cliques, and dense cliques, arising in cohesive subgraph extraction applications. However, the $f(\cdot)$-dense graph may be disconnected or weakly connected. To conquer this, we study the problem of finding the largest $f(\cdot)$-dense subgraph with a diameter of at most two in the paper. Specifically, we present a decomposition-based branch-and-bound algorithm to optimally solve this problem. The key feature of the algorithm is a decomposition framework that breaks the graph into $n$ smaller subgraphs, allowing independent searches in each subgraph. We also introduce decomposition strategies including degeneracy and two-hop degeneracy orderings, alongside a branch-and-bound algorithm with a novel sorting-based upper bound to solve each subproblem. Worst-case complexity for each component is provided. Empirical results on 139 real-world graphs under two $f(\cdot)$ functions show our algorithm outperforms the MIP solver and pure branch-and-bound, solving nearly twice as many instances optimally within one hour.Open AccessA Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems
A graph with $n$ vertices is an $f(\cdot)$-dense graph if it has at least $f(n)$ edges, $f(\cdot)$ being a well-defined function. The notion $f(\cdot)$-dense graph encompasses various clique models like $γ$-quasi cliques, $k$-defective cliques, and dense cliques, arising in cohesive subgraph extraction applications. However, the $f(\cdot)$-dense graph may be disconnected or weakly connected. To conquer this, we study the problem of finding the largest $f(\cdot)$-dense subgraph with a diameter of at most two in the paper. Specifically, we present a decomposition-based branch-and-bound algorithm to optimally solve this problem. The key feature of the algorithm is a decomposition framework that breaks the graph into $n$ smaller subgraphs, allowing independent searches in each subgraph. We also introduce decomposition strategies including degeneracy and two-hop degeneracy orderings, alongside a branch-and-bound algorithm with a novel sorting-based upper bound to solve each subproblem. Worst-case complexity for each component is provided. Empirical results on 139 real-world graphs under two $f(\cdot)$ functions show our algorithm outperforms the MIP solver and pure branch-and-bound, solving nearly twice as many instances optimally within one hour.