10 citations · 13 across the 9 of their papers we have counts for
7 papers · 1 filter
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…
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…