MADALGO Theory Seminar

MADALGO Seminar: Karl Bringmann (Max-Planck-Institut für Informatik): "Improved Pseudopolynomial Time Algorithms for Subset Sum"

2016.08.09 | Katrine Østerlund Rasmussen

Date Wed 17 Aug
Time 14:15 15:00
Location Nygaard-327

Title
Improved Pseudopolynomial Time Algorithms for Subset Sum

Abstract
Given a set Z of n positive integers and a target value t, the SubsetSum problem asks whether any subset of Z sums to t. A textbook pseudopolynomial time algorithm by Bellman from 1957 solves SubsetSum in time O(nt). Here we present a simple and elegant randomized algorithm running in time soft-O(n+t). This improves upon a classic result and is likely to be near-optimal, since it matches  conditional lower bounds from SetCover and k-Clique. We also present a new algorithm with pseudopolynomial time and polynomial space. 

Host
Kasper Green Larsen

Seminar