Solving Subset Sum via additive combinatoricsOberseminar Discrete Optimization

by Prof. Guochuan Zhang (Zhejiang University, Hangzhou)

Monday Jun 2, 2025, 6:15 PM → 7:15 PM Europe/Berlin

Arithmeum, Lennéstr., 2 - Seminarraum (Arithmeum / Research Institute for Discrete Mathematics)

In the subset sum problem (Subset Sum), given a multi-set of positive integers and a target, the goal is to determine whether there exists a subset of the integers that sums to the target. 

I will talk about recent results in approximation schemes and exact algorithms for Subset Sum. More precisely, a weak approximation scheme is provided, which runs in nearly linear time, and a faster pseudo-polynomial time algorithm is presented. The progress is based on additive combinatorics results on arithmetic progressions.

 

This talk is based on joint papers with Lin Chen, Jiayi Lian and Yuchen Mao.

 

The Oberseminar takes place in the Seminarraum, 1^st floor. Participants are invited to have coffee or tea in the lounge before.