Showing 2024Show all
2 papers · 1 filter
cs.DS2024
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…
cs.DS2024
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…