Xiao Mao

activity

20162026

most citedApproximating Knapsack and Partition via Dense Subset Sums

10 citations · 13 across the 9 of their papers we have counts for

collaborators

Showing 2023Show all

3 papers · 1 filter

cs.DS2023

$(1 - ε)$ -Approximation of Knapsack in Nearly Quadratic Time

Xiao Mao

Knapsack is one of the most fundamental problems in theoretical computer science. In the $(1 - ε)$ -approximation setting, although there is a fine-grained lower bound of $(n + 1 /…

cs.DS2023

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 $n$ -vertex graph.…

cs.DS2023★ 10 cited

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 $(1 - ε)$ -approximation setting are not yet settled. In this work, we make…

(1−ε)-Approximation of Knapsack in Nearly Quadratic Time

Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time

Approximating Knapsack and Partition via Dense Subset Sums

$(1 - ε)$ -Approximation of Knapsack in Nearly Quadratic Time