Campus Event Calendar
Event Entry
What and Who
Faster Space Efficient Algorithms for Subset Sum and Knapsack
Jesper Nederlof
Eindhoven University of Technology
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 31 January 2017
13:00
30 Minutes
E1 4 - MPI-INF
024
Saarbrücken
Abstract
We present a randomized Monte Carlo algorithm that solves a given instance of Subset Sum on n integers using O*(2^{0.86n}) time and O*(1) space, where O*() suppresses factors polynomial in the input size. The algorithm assumes random access to the random bits used. The same result can be obtained for Knapsack on n items, and the same methods also have consequences for the k-Sum problem. Joint work with Nikhil Bansal, Shashwat Garg and Nikhil Vyas.
Contact
Holger Dell
--email hidden
passcode not visible
logged in users only
Holger Dell, 01/11/2017 19:04 -- Created document.