YZYi Zhou

Yi Zhou

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Yi Zhou has a total of 56 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • A Reduction-Driven Local Search for the Generalized Independent Set Problem

    by Yiping Liu, Yi Zhou, Zhenxiang Xu, Mingyu Xiao, Jin-Kao Hao

    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/ .

  • Code and Data Repository for A Reduction-Driven Local Search for the Generalized Independent Set Problem

    by Yiping Liu, Yi Zhou, Zhenxiang Xu, Mingyu Xiao, Jin-Kao Hao

    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

    Graph downsizing: a fast heuristic for querying closely connected subgraphs

    by Yiping Liu, Mengxiao Zhang, Jiamou Liu, Yi Zhou

    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$$ τ < n , find an induced subgraph of size $$n-\tau $$ n - τ 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

    by Haoji Zhang, Yuzhe Li, Zhenqiang Liu, Chenyang Liu, Shenyang Zhang, Yi Zhou

    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

    by Yi Zhou, Haoyu Jiang, Chenghao Zhu, André Rossi

    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.

  • Fast exact algorithms for the maximum diversity problem

    by Jinping Lei, Lu Liu, Mingyu Xiao, Yi Zhou

  • Open Access

    A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems

    by Yi Zhou, Chunyu Luo, Zhengren Wang, Zhang-Hua Fu

    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.