Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Improved Pseudopolynomial Time Algorithms for Subset Sum
Speaker:Karl Bringmann
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 4 August 2016
Duration:30 Minutes
Building:E1 4
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.
Name(s):Karl Bringmann
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
Karl Bringmann, 07/27/2016 02:55 PM
Last modified:
Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Karl Bringmann, 07/27/2016 02:55 PM -- Created document.