Speaker:
Chao Xu(The Voleon Group)
Time:
- 11:00AM(Time in Beijing)
- 4:00PM(Time in Auckland)
- January 6, 2021 (Wednesday)
VooVmeeting
ID：360572001 Password: 1936
Link:
https://meeting.tencent.com/s/Hu6RyhQq2MPc
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.
Organizers:
Bakhadyr Khoussainov, Jiamou Liu, and Mingyu Xiao