An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem

DOI10.1137/0220072zbMath0736.68041OpenAlexW2069650774MaRDI QIDQ3985814

Olded Margalit, Zvi Galil

Publication date: 27 June 1992

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0220072

zbMATH Keywords

integer programmingNP-hardsubset-sumdense problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of partitions of integers (05A17) Permutations, words, matrices (05A05) Number-theoretic algorithms; complexity (11Y16) Elementary theory of partitions (11P81) Density, gaps, topology (11B05) Arithmetic progressions (11B25)

Related Items (8)

Scheduling lower bounds via AND subset sum ⋮ Complement, Complexity, and Symmetric Representation ⋮ Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach ⋮ Counting subset sums of finite Abelian groups ⋮ When subset-sums do not cover all the residues modulo \(p\). ⋮ Subset Sum Quantumly in 1.17 n . ⋮ Moment subset sums over finite fields ⋮ Faster Pseudopolynomial Time Algorithms for Subset Sum

This page was built for publication: An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem