5 papers
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…
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…
Bridging the Data Gap in AI Reliability Research and Establishing DR-AIR, a Comprehensive Data Repository for AI Reliability
Simin Zheng, Jared M. Clark, Fatemeh Salboukh +10
Artificial intelligence (AI) technology and systems have been advancing rapidly. However, ensuring the reliability of these systems is crucial for fostering public confidence in th…
A Note on Deterministic FPTAS for Partition
Lin Chen, Jiayi Lian, Yuchen Mao +1
We consider the Partition problem and propose a deterministic FPTAS (Fully Polynomial-Time Approximation Scheme) that runs in -time. This is the b…
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…