Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum
Karl Bringmann, Vasileios Nakos
Abstract
In the classical SubsetSum problem we are given a set X and a target t, and the task is to decide whether there exists a subset of X which sums to t. A recent line of research has resulted in (t · poly (logt))-time algorithms, which are (near-)optimal under popular complexity-theoretic assumptions. On the other hand, the standard dynamic programming algorithm runs in time O(n · |S(X,t)|), where S(X,t) is the set of all subset sums of X that are smaller than t. All previous pseudopolynomial algorithms actually solve a stronger task, since they actually compute the whole set S(X,t).
Topics & Concepts
Set (abstract data type)Task (project management)Convolution (computer science)Computer scienceSubset sum problemTime complexityAlgorithmLine (geometry)Computational complexity theoryDynamic programmingDiscrete mathematicsLinear programmingCombinatoricsMathematicsArtificial intelligenceEconomicsManagementKnapsack problemArtificial neural networkProgramming languageGeometryComplexity and Algorithms in GraphsMachine Learning and AlgorithmsAlgorithms and Data Compression