4 citations · 9 across the 10 of their papers we have counts for
6 papers · 1 filter
Weakly Approximating Knapsack in Subquadratic Time
Lin Chen, Jiayi Lian, Yuchen Mao +1
We consider the classic Knapsack problem. Let and be the capacity and the optimal value, respectively. If one seeks a solution with total profit at least $\mathr…
Approximating Partition in Deterministic Near-Linear Time
Lin Chen, Jiayi Lian, Yuchen Mao +1
We propose a deterministic -time FPTAS (Fully Polynomial-Time Approximation Scheme) for the classical Partition problem. This is the best possible (up…
An Improved Pseudopolynomial Time Algorithm for Subset Sum
Lin Chen, Jiayi Lian, Yuchen Mao +1
We investigate pseudo-polynomial time algorithms for Subset Sum. Given a multi-set of positive integers and a target , Subset Sum asks whether some subset of sums to…
Approximating Partition in Near-Linear Time
Lin Chen, Jiayi Lian, Yuchen Mao +1
We propose an $\widetilde{O}(n + 1/\eps)$-time FPTAS (Fully Polynomial-Time Approximation Scheme) for the classical Partition problem. This is the best possible (up to a polylogari…
A Nearly Quadratic-Time FPTAS for Knapsack
Lin Chen, Jiayi Lian, Yuchen Mao +1
We investigate the classic Knapsack problem and propose a fully polynomial-time approximation scheme (FPTAS) that runs in time. This improves…
Faster Algorithms for Bounded Knapsack and Bounded Subset Sum Via Fine-Grained Proximity Results
Lin Chen, Jiayi Lian, Yuchen Mao +1
We investigate pseudopolynomial-time algorithms for Bounded Knapsack and Bounded Subset Sum. Recent years have seen a growing interest in settling their fine-grained complexity wit…