Author name cluster

Zhihuai Chen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

AAAI Conference 2024 Conference Paper

Threshold-Based Responsive Simulated Annealing for Directed Feedback Vertex Set Problem

Qingyun Zhang
Yuming Du
Zhouxing Su
Chu-Min Li
Junzhou Xu
Zhihuai Chen
Zhipeng Lü

As a classical NP-hard problem and the topic of the PACE 2022 competition, the directed feedback vertex set problem (DFVSP) aims to find a minimum subset of vertices such that, when vertices in the subset and all their adjacent edges are removed from the directed graph, the remainder graph is acyclic. In this paper, we propose a threshold-based responsive simulated annealing algorithm called TRSA for solving DFVSP. First, we simplify the problem instances with two new reduction rules proposed in this paper and eight reduction rules from the literature. Then, based on a new solution representation, TRSA solves DFVSP with a fast local search procedure featured by a swap-based neighborhood structure and three neighborhood acceleration strategies. Finally, all these strategies are incorporated into a threshold-based responsive simulated annealing framework. Computational experiments on 140 benchmark instances show that TRSA is highly competitive compared to the state-of-the-art methods. Specifically, TRSA can improve the best known results for 53 instances, while matching the best known results for 79 ones. Furthermore, some important features of TRSA are analyzed to identify its success factors.

PDF Details DOI

TCS Journal 2020 Journal Article

Facility location games with optional preference

Zhihuai Chen
Ken C.K. Fong
Minming Li
Kai Wang
Hongning Yuan
Yong Zhang

In this paper, we study the optional preference model of the facility location game problem with two heterogeneous facilities on a line. The preference of each agent is one of the two facilities or both facilities, and the cost of each agent is a function of the distances to the facilities that the agent prefers. We consider two cost functions: Minimum Distance and Maximum Distance functions. Aiming at minimizing the maximum cost or the social cost of agents, we propose different strategyproof mechanisms without monetary transfers and derive both lower and upper bounds of the approximation ratios with respect to strategyproof mechanisms. In the variant of Minimum Distance, we propose a 2-approximation deterministic strategyproof mechanism for the maximum cost objective, and prove a lower bound of 4/3, while for the social cost objective we propose a ( n / 2 +1)-approximation deterministic strategyproof mechanism and prove a lower bound of 2, also a lower bound of 3/2 for randomized mechanisms. In the variant of Maximum Distance, we propose an optimal deterministic strategyproof mechanism for the maximum cost objective and a 2-approximation deterministic strategyproof mechanism for the social cost objective.

Details DOI

IJCAI Conference 2019 Conference Paper

A Quantum-inspired Classical Algorithm for Separable Non-negative Matrix Factorization

Zhihuai Chen
Yinan Li
Xiaoming Sun
Pei Yuan
Jialin Zhang

Non-negative Matrix Factorization (NMF) asks to decompose a (entry-wise) non-negative matrix into the product of two smaller-sized nonnegative matrices, which has been shown intractable in general. In order to overcome this issue, separability assumption is introduced which assumes all data points are in a conical hull. This assumption makes NMF tractable and widely used in text analysis and image processing, but still impractical for huge-scale datasets. In this paper, inspired by recent development on dequantizing techniques, we propose a new classical algorithm for separable NMF problem. Our new algorithm runs in polynomial time in the rank and logarithmic in the size of input matrices, which achieves an exponential speedup in the low-rank setting.

PDF Details