2 papers
cs.DS2024
Approximately Counting Knapsack Solutions in Subquadratic Time
Weiming Feng, Ce Jin
We revisit the classic #Knapsack problem, which asks to count the Boolean points in a given half-space . This #P-complete pro…
cs.DS2024
A Faster Algorithm for Pigeonhole Equal Sums
Ce Jin, Hongxun Wu
An important area of research in exact algorithms is to solve Subset-Sum-type problems faster than meet-in-middle. In this paper we study Pigeonhole Equal Sums, a total search prob…