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

DOI10.1137/0220072MaRDI QIDQ3985814zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• scientific article; zbMATH DE number 176777
• Solving dense subset-sum problems by using analytical number theory
• STACS 2005
• Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach

Cited in

(23)

• Dense subset sum may be the hardest
• scientific article; zbMATH DE number 139903 (Why is no real title available?)
• A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Complement, complexity, and symmetric representation
• Scheduling lower bounds via AND subset sum
• When subset-sums do not cover all the residues modulo \(p\).
• An Improved Multi-set Algorithm for the Dense Subset Sum Problem
• STACS 2005
• Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach
• Subset Sum Quantumly in 1.17 n .
• Fast n-fold Boolean convolution via additive combinatorics
• Knapsack and subset sum with small items
• Scheduling lower bounds via and subset sum
• An Average-Case Sublinear Exact Li and Stephens Forward Algorithm
• Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum
• A faster pseudopolynomial time algorithm for subset sum
• Does subset sum admit short proofs?
• Moment subset sums over finite fields
• Exact algorithms for problems related to the densest \(k\)-set problem
• Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence
• scientific article; zbMATH DE number 4149895 (Why is no real title available?)
• scientific article; zbMATH DE number 176777 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3985814)