10 citations · 13 across the 9 of their papers we have counts for
11 papers
Subset Sum in Almost-Linear Time
Ce Jin, Xiao Mao
We give a deterministic algorithm for finding a subset of the input integers that sums to the target in time. This impro…
-Approximation of Knapsack in Nearly Quadratic Time
Xiao Mao
Knapsack is one of the most fundamental problems in theoretical computer science. In the -approximation setting, although there is a fine-grained lower bound of $(n + 1 /…
Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
Xiao Mao
The All-Pairs Shortest Paths (APSP) problem is one of the fundamental problems in theoretical computer science. It asks to compute the distance matrix of a given -vertex graph.…
Approximating Knapsack and Partition via Dense Subset Sums
Mingyang Deng, Ce Jin, Xiao Mao
Knapsack and Partition are two important additive problems whose fine-grained complexities in the -approximation setting are not yet settled. In this work, we make…
DL-DRL: A double-level deep reinforcement learning approach for large-scale task scheduling of multi-UAV
Xiao Mao, Zhiguang Cao, Mingfeng Fan +2
Exploiting unmanned aerial vehicles (UAVs) to execute tasks is gaining growing popularity recently. To solve the underlying task scheduling problem, the deep reinforcement learning…
On Problems Related to Unbounded SubsetSum: A Unified Combinatorial Approach
Mingyang Deng, Xiao Mao, Ziqian Zhong
Unbounded SubsetSum is a classical textbook problem: given integers , we need to find if there exists satisfyin…
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance
Xiao Mao
The (unweighted) tree edit distance problem for node trees asks to compute a measure of dissimilarity between two rooted trees with node labels. The current best algorithm from…
Shortest non-separating st-path on chordal graphs
Xiao Mao
Many NP-Hard problems on general graphs, such as maximum independence set, maximal cliques and graph coloring can be solved efficiently on chordal graphs. In this paper, we explore…
A natural extension to the convex hull problem and a novel solution
Xiao Mao
We study a natural extension to the well-known convex hull problem by introducing multiplicity: if we are given a set of convex polygons, and we are allowed to partition the set in…
Integrating Coarse Granularity Part-level Features with Supervised Global-level Features for Person Re-identification
Xiaofei Mao, Jiahao Cao, Dongfang Li +2
Holistic person re-identification (Re-ID) and partial person re-identification have achieved great progress respectively in recent years. However, scenarios in reality often includ…
Knapsack problem for automaton groups
Thibault Godin
The knapsack problem is a classic optimisation problem that has been recently extended in the setting of groups. Its study reveals to be interesting since it provides many differen…