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:Subquadratic Approximation Scheme for Partition
Speaker:Karol Węgrzycki
coming from:University of Warsaw
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 24 April 2018
Duration:30 Minutes
Building:E1 4
The subject of this paper is the time complexity of approximating Knapsack, Subset Sum, Partition, and some other related problems. The main result is an O˜(n + 1/ε^{5/3}) time randomized FPTAS for Partition, which is derived from a certain relaxed form of a randomized FPTAS for Subset Sum. To the best of our knowledge, this is the first NP-hard problem that has been shown to admit a subquadratic time approximation scheme, i.e., one with time complexity of O((n + 1/ε)^{2−δ}) for some δ>0. To put these developments in context, note that a quadratic FPTAS for Partition has been known for 40 years.

Our main contribution lies in designing a mechanism that reduces an instance of Subset Sum to several simpler instances, each with some special structure, and keeps track of interactions between them. This allows us to combine techniques from approximation algorithms, pseudo-polynomial algorithms, and additive combinatorics.
We also prove several related results. Notably, we improve approximation schemes for 3-SUM, (min,+)-convolution, and Tree Sparsity. Finally, we argue why breaking the quadratic barrier for approximate Knapsack is unlikely by giving an Ω((n + 1/ε)^{2−o(1)}) conditional lower bound.

Name(s):Karl Bringmann
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Karl Bringmann, 04/12/2018 10:05 AM
Last modified:
Uwe Brahm/MPII/DE, 04/13/2018 07:01 AM
  • Karl Bringmann, 04/12/2018 10:06 AM
  • Karl Bringmann, 04/12/2018 10:05 AM -- Created document.