N&O Lecture Jesper Nederlof (TU/e): Faster Space Efficient Algorithms for Subset Sum and Knapsack
Everyone is welcome to attend the public lecture of Jesper Nederlof. Abstract: Faster Space Efficient Algorithms for Subset Sum and KnapsackWe 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.
- https://www.cwi.nl/events/2017/n-o-lectures-2017/no-lecture-jesper-nederlof-tue-faster-space-efficient-algorithms-subset-sum-and-knapsack
- N&O Lecture Jesper Nederlof (TU/e): Faster Space Efficient Algorithms for Subset Sum and Knapsack
- 2017-02-08T10:00:00+01:00
- 2017-02-08T11:00:00+01:00
- Everyone is welcome to attend the public lecture of Jesper Nederlof. Abstract: Faster Space Efficient Algorithms for Subset Sum and KnapsackWe 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.
- What Networks & Optimization
- When Feb 08, 2017 from 10:00 AM to 11:00 AM (Europe/Amsterdam / UTC100)
- Where Room L016 - CWI
- Web Visit external website
- Add event to calendar iCal
Everyone is welcome to attend the public lecture of Jesper Nederlof. Abstract:
Faster Space Efficient Algorithms for Subset Sum and Knapsack
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.