A simple deterministic pseudopolynomial time algorithms for subset sum
- Speaker
- Chao Xu
- Affiliation
- The Voleon Group
- Date
- Time
- Asia/Shanghai
- Venue
- Online, VooV meeting ID: 360572001
Abstract
Given a set of n positive integers and a target integer t, the subset sum problem asks if there exists a subset with elements sum to t. Bellman (1956) found a dynamic programming algorithm that solves the problem in $O(nt)$ time. There were no significant improvements in running time until Koiliaris and Xu (2017) gave a $\tilde{O}(\sqrt{n}t, t^{4/3})$ time algorithm based on exponentially growing partitions. Since then, multiple papers on the topic come out each year.
We give a survey of the recent progress on pseudopolynomial time algorithms for subset sum and its extensions, and describes a much simplified and improved deter-ministic algorithm by Koiliaris and Xu (2019) with running time $\tilde{O}(\sqrt{n}t, t^{5/4})$. The algorithm achieves $\tilde{O}(\sqrt{n}t)$ by choosing a better partitioning strategy (partition by congruence), so the entire algorithm and its analysis fits in a single page.
Schedule
- 11:00AM(Time in Beijing)
- 4:00PM(Time in Auckland)
- January 6, 2021 (Wednesday)
Online Meeting
ID：360572001 Password: 1936
https://meeting.tencent.com/s/Hu6RyhQq2MPc
Organizers
Bakhadyr Khoussainov, Jiamou Liu, and Mingyu Xiao