Campus Event Calendar
Event Entry
What and Who
Improved Pseudopolynomial Time Algorithms for Subset Sum
Karl Bringmann
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 4 August 2016
13:00
30 Minutes
E1 4
024
Saarbrücken
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.
Contact
Karl Bringmann
--email hidden
passcode not visible
logged in users only
Karl Bringmann, 07/27/2016 14:55 -- Created document.