Chenhao Wang
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Chenhao Wang has a total of 57 co-authors. Here are the top co-authors by number of shared publications:
Hau Chan
11 shared publicationsZhongzheng Tang
Beijing University of Posts and Telecommunications
8 shared publications- Zhongzheng Tang
School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing, China
8 shared publications Xujin Chen
7 shared publicationsMinming Li
6 shared publications- Mengqi Zhang
Chinese Academy of Sciences
5 shared publications
Latest Publications
- Open Access
- 17 September 2026
- Published by Elsevier in SSRN Electronic Journal
A 3.7321-Competitive Algorithm for Matroid Secretary
The matroid secretary problem asks an online algorithm to select a high-weight independent set from elements arriving in uniformly random order, with immediate and irrevocable decisions. Singla (2026) recently gave a 4-competitive algorithm for arbitrary matroids using only the number of elements and independence queries on already-arrived elements. Following his approach, we obtain an improved competitive ratio of 2 + √ 3 ≈ 3.7321 in the same information model. Our algorithm accepts every element of a fixed canonical optimum with probability at least 2-√ 3 and uses O(n 2) independence queries. The algorithm modifies Singla's reversible reference process by retaining a randomly chosen part of the sample as a reserve whose membership in the reference greedy solution is not frozen. Balancing the remaining sample and post-sample elements preserves reversibility and allows an exact calculation of the probability that an exchange partner blocks a target element. The resulting guarantee has a direct analytic proof.
- 17 September 2026
- Published by Elsevier in SSRN Electronic Journal
Open AccessA 3.7321-Competitive Algorithm for Matroid Secretary
The matroid secretary problem asks an online algorithm to select a high-weight independent set from elements arriving in uniformly random order, with immediate and irrevocable decisions. Singla (2026) recently gave a 4-competitive algorithm for arbitrary matroids using only the number of elements and independence queries on already-arrived elements. Following his approach, we obtain an improved competitive ratio of 2 + √ 3 ≈ 3.7321 in the same information model. Our algorithm accepts every element of a fixed canonical optimum with probability at least 2-√ 3 and uses O(n 2) independence queries. The algorithm modifies Singla's reversible reference process by retaining a randomly chosen part of the sample as a reserve whose membership in the reference greedy solution is not frozen. Balancing the remaining sample and post-sample elements preserves reversibility and allows an exact calculation of the probability that an exchange partner blocks a target element. The resulting guarantee has a direct analytic proof.
- Open Access
- 10 September 2026
- Published by Elsevier in SSRN Electronic Journal
Sequential Phragmén Guarantees 2-Approximate Core Stability
In an approval-based committee election, a committee of size k is selected from a set of candidates to represent voters of total weight n, each of whom has positive weight and approves a subset of the candidates. A size-k committee is λ-stable if, for every nonempty subset T of candidates, the total weight of voters who strictly prefer T is less than λ times the proportional share n|T |/k. Whether there exists a committee that is exactly stable, corresponding to λ = 1, remains a major open problem in approval-based committee voting. Thus, a natural objective is to identify small values of λ > 1 for which λ-stability can always be guaranteed. We prove that weighted sequential Phragmén, a classical and natural rule, always returns a 2-stable committee of size k. Since the λ-core is the set of all λ-stable committees, our result implies that the 2-core is always nonempty. This improves upon the previously best-known guarantee, due to Gao, Sun, and Vondrák [EC 2026], that a 3.651-stable committee always exists.
- 10 September 2026
- Published by Elsevier in SSRN Electronic Journal
Open AccessSequential Phragmén Guarantees 2-Approximate Core Stability
In an approval-based committee election, a committee of size k is selected from a set of candidates to represent voters of total weight n, each of whom has positive weight and approves a subset of the candidates. A size-k committee is λ-stable if, for every nonempty subset T of candidates, the total weight of voters who strictly prefer T is less than λ times the proportional share n|T |/k. Whether there exists a committee that is exactly stable, corresponding to λ = 1, remains a major open problem in approval-based committee voting. Thus, a natural objective is to identify small values of λ > 1 for which λ-stability can always be guaranteed. We prove that weighted sequential Phragmén, a classical and natural rule, always returns a 2-stable committee of size k. Since the λ-core is the set of all λ-stable committees, our result implies that the 2-core is always nonempty. This improves upon the previously best-known guarantee, due to Gao, Sun, and Vondrák [EC 2026], that a 3.651-stable committee always exists.
- Open Access
- 8 August 2026
- Published by Association for Computing Machinery (ACM)
- p. 3715-3726
PG-DyRA: Potential-Game Guided Multi-Agent Collaboration for Dynamic Urban Resource Allocation
- 8 August 2026
- Published by Association for Computing Machinery (ACM)
- p. 3715-3726
Open AccessPG-DyRA: Potential-Game Guided Multi-Agent Collaboration for Dynamic Urban Resource Allocation
- 27 April 2026
- Published by Springer Nature in Autonomous Agents and Multi-Agent Systems
- Vol. 40 (1) , 22
Strategyproof facility location with prediction: minimizing the maximum cost
- 27 April 2026
- Published by Springer Nature in Autonomous Agents and Multi-Agent Systems
- Vol. 40 (1) , 22
Strategyproof facility location with prediction: minimizing the maximum cost
- 12 April 2026
- Published by Elsevier in Knowledge-Based Systems
- Vol. 343
BLADE: Brainstorming LLMs as algorithm designer through evolution for online subset selection
- 12 April 2026
- Published by Elsevier in Knowledge-Based Systems
- Vol. 343
BLADE: Brainstorming LLMs as algorithm designer through evolution for online subset selection
- 10 October 2025
- Published by Springer Nature in Annals of Operations Research
- Vol. 356 (2-3) , 1231-1280
Improving the location of facilities through network addition modification: a revisit
- 10 October 2025
- Published by Springer Nature in Annals of Operations Research
- Vol. 356 (2-3) , 1231-1280
Improving the location of facilities through network addition modification: a revisit
- Open Access
- 11 April 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 39 (13) , 13691-13699
Mechanism Design for Connecting Regions Under Disruptions
Man-made and natural disruptions such as planned constructions on roads, suspensions of bridges, and blocked roads by trees/mudslides/floods can often create obstacles that separate two connected regions. As a result, the traveling and reachability of agents from their respective regions to other regions can be affected. To minimize the impact of the obstacles and maintain agent accessibility, we initiate the problem of constructing a new pathway (e.g., a detour or new bridge) connecting the regions disconnected by obstacles from the mechanism design perspective. In the problem, each agent in their region has a private location and is required to access the other region. The cost of an agent is the distance from their location to the other region via the pathway. Our goal is to design strategyproof mechanisms that elicit truthful locations from the agents and approximately optimize the social or maximum cost of agents by determining locations in the regions for building a pathway. We provide a characterization of all strategyproof and anonymous mechanisms. For the social and maximum costs, we provide upper and lower bounds on the approximation ratios of strategyproof mechanisms.
- 11 April 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 39 (13) , 13691-13699
Open AccessMechanism Design for Connecting Regions Under Disruptions
Man-made and natural disruptions such as planned constructions on roads, suspensions of bridges, and blocked roads by trees/mudslides/floods can often create obstacles that separate two connected regions. As a result, the traveling and reachability of agents from their respective regions to other regions can be affected. To minimize the impact of the obstacles and maintain agent accessibility, we initiate the problem of constructing a new pathway (e.g., a detour or new bridge) connecting the regions disconnected by obstacles from the mechanism design perspective. In the problem, each agent in their region has a private location and is required to access the other region. The cost of an agent is the distance from their location to the other region via the pathway. Our goal is to design strategyproof mechanisms that elicit truthful locations from the agents and approximately optimize the social or maximum cost of agents by determining locations in the regions for building a pathway. We provide a characterization of all strategyproof and anonymous mechanisms. For the social and maximum costs, we provide upper and lower bounds on the approximation ratios of strategyproof mechanisms.
- Top Cited PapersOpen Access
- 4 April 2025
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 57 (9) , 1-39
Empowering Edge Intelligence: A Comprehensive Survey on On-Device AI Models
The rapid advancement of artificial intelligence (AI) technologies has led to an increasing deployment of AI models on edge and terminal devices, driven by the proliferation of the Internet of Things (IoT) and the need for real-time data processing. This survey comprehensively explores the current state, technical challenges, and future trends of on-device AI models. We define on-device AI models as those designed to perform local data processing and inference, emphasizing their characteristics such as real-time performance, resource constraints, and enhanced data privacy. The survey is structured around key themes, including the fundamental concepts of AI models, application scenarios across various domains, and technical challenges faced in edge environments. We also discuss optimization and implementation strategies, such as data preprocessing, model compression, and hardware acceleration, which are essential for effective deployment. Furthermore, we examine the impact of emerging technologies, including edge computing and foundation models, on the evolution of on-device AI models. By providing a structured overview of the challenges, solutions, and future directions, this survey aims to facilitate further research and application of on-device AI, ultimately contributing to the advancement of intelligent systems in everyday life.
- 4 April 2025
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 57 (9) , 1-39
Top Cited PapersOpen AccessEmpowering Edge Intelligence: A Comprehensive Survey on On-Device AI Models
The rapid advancement of artificial intelligence (AI) technologies has led to an increasing deployment of AI models on edge and terminal devices, driven by the proliferation of the Internet of Things (IoT) and the need for real-time data processing. This survey comprehensively explores the current state, technical challenges, and future trends of on-device AI models. We define on-device AI models as those designed to perform local data processing and inference, emphasizing their characteristics such as real-time performance, resource constraints, and enhanced data privacy. The survey is structured around key themes, including the fundamental concepts of AI models, application scenarios across various domains, and technical challenges faced in edge environments. We also discuss optimization and implementation strategies, such as data preprocessing, model compression, and hardware acceleration, which are essential for effective deployment. Furthermore, we examine the impact of emerging technologies, including edge computing and foundation models, on the evolution of on-device AI models. By providing a structured overview of the challenges, solutions, and future directions, this survey aims to facilitate further research and application of on-device AI, ultimately contributing to the advancement of intelligent systems in everyday life.
- Open Access
- 3 January 2025
- Published by Science China Press., Co. Ltd. in SCIENTIA SINICA Mathematica
- Vol. 55 (2) , 199
The equilibrium existence of strategic influence games in social networks
本文基于 Grabisch 等人 2010 年提出的社交网络影响力博弈模型展开研究. 在一个强连通网络中, 每个顶点被称为一个(社交网络)成员, 每个成员都有一个位于 [0, 1] 中的数字表示他的初始观点, 并且该观点可以动态演变. 博弈在两个博弈人之间展开, 其分别具有固定的观点 0 和 1; 他们分别选择一个成员作为自己的影响目标, 使得其影响力通过网络中成员之间的相互作用而传播, 从而影响整个社交网络中所有成员的观点. 博弈人的目标是使全体成员的平均观点(值)尽可能接近自己的固有观点 (0 或 1). 本文引入一个新的影响力传播矩阵来刻画博弈人对成员的影响作用, ,当两个局中人具有相同影响力时, 给出了纳什均衡存在的充分条件, 并证明了在具有均匀权重的双向树网络中纳什均衡一定存在. 对网络实例特别是随机网络的模拟实验结果显示: 与 Grabisch 等人模型相比, 新的影响力传播矩阵放宽了一系列网络中纳什均衡的存在性条件.
- 3 January 2025
- Published by Science China Press., Co. Ltd. in SCIENTIA SINICA Mathematica
- Vol. 55 (2) , 199
Open AccessThe equilibrium existence of strategic influence games in social networks
本文基于 Grabisch 等人 2010 年提出的社交网络影响力博弈模型展开研究. 在一个强连通网络中, 每个顶点被称为一个(社交网络)成员, 每个成员都有一个位于 [0, 1] 中的数字表示他的初始观点, 并且该观点可以动态演变. 博弈在两个博弈人之间展开, 其分别具有固定的观点 0 和 1; 他们分别选择一个成员作为自己的影响目标, 使得其影响力通过网络中成员之间的相互作用而传播, 从而影响整个社交网络中所有成员的观点. 博弈人的目标是使全体成员的平均观点(值)尽可能接近自己的固有观点 (0 或 1). 本文引入一个新的影响力传播矩阵来刻画博弈人对成员的影响作用, ,当两个局中人具有相同影响力时, 给出了纳什均衡存在的充分条件, 并证明了在具有均匀权重的双向树网络中纳什均衡一定存在. 对网络实例特别是随机网络的模拟实验结果显示: 与 Grabisch 等人模型相比, 新的影响力传播矩阵放宽了一系列网络中纳什均衡的存在性条件.
- Open Access
- 16 October 2024
- Published by IOS Press
- p. 3453-3460
Mechanism Design for Extending the Accessibility of Facilities
We study a variation of facility location problems (FLPs) that aims to improve the accessibility of agents to the facility within the context of mechanism design without money. In such a variation, agents have preferences on the ideal locations of the facility on a real line, and the facility’s location is fixed in advance where (re)locating the facility is not possible due to various constraints (e.g., limited space and construction costs). To improve the accessibility of agents to facilities, existing mechanism design literature in FLPs has proposed to structurally modify the real line (e.g., by adding a new interval) or provide shuttle services between two points when structural modifications are not possible. In this paper, we focus on the latter approach and propose to construct an accessibility range to extend the accessibility of the facility. In the range, agents can receive accommodations (e.g., school buses, campus shuttles, or pickup services) to help reach the facility. Therefore, the cost of each agent is the distance from their ideal location to the facility (possibility) through the range. We focus on designing strategyproof mechanisms that elicit true ideal locations from the agents and construct accessibility ranges (intervals) to approximately minimize the social cost or the maximum cost of agents. For both social and maximum costs, we design group strategyproof mechanisms and strong group strategyproof mechanisms with (asymptotically) tight bounds on the approximation ratios.
- 16 October 2024
- Published by IOS Press
- p. 3453-3460
Open AccessMechanism Design for Extending the Accessibility of Facilities
We study a variation of facility location problems (FLPs) that aims to improve the accessibility of agents to the facility within the context of mechanism design without money. In such a variation, agents have preferences on the ideal locations of the facility on a real line, and the facility’s location is fixed in advance where (re)locating the facility is not possible due to various constraints (e.g., limited space and construction costs). To improve the accessibility of agents to facilities, existing mechanism design literature in FLPs has proposed to structurally modify the real line (e.g., by adding a new interval) or provide shuttle services between two points when structural modifications are not possible. In this paper, we focus on the latter approach and propose to construct an accessibility range to extend the accessibility of the facility. In the range, agents can receive accommodations (e.g., school buses, campus shuttles, or pickup services) to help reach the facility. Therefore, the cost of each agent is the distance from their ideal location to the facility (possibility) through the range. We focus on designing strategyproof mechanisms that elicit true ideal locations from the agents and construct accessibility ranges (intervals) to approximately minimize the social cost or the maximum cost of agents. For both social and maximum costs, we design group strategyproof mechanisms and strong group strategyproof mechanisms with (asymptotically) tight bounds on the approximation ratios.