An almost linear-time algorithm for the dense subset-sum problem

DOI10.1007/3-540-54233-7_177MaRDI QIDQ4036607zbMATH OpenFDO

Authors Olded Margalit, Zvi Galil

Publication date 18 May 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-54233-7_177

zbMATH Keywords

almost linear-time algorithmdense subset-sum problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10)

Recommendations

• An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem
• 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
• Improved low-density subset sum algorithms

Cited in

(19)

• A branch bound method for subset sum problem
• On variations of the subset sum problem
• 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
• A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
• scientific article; zbMATH DE number 4149895 (Why is no real title available?)
• Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach
• On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem
• An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem
• scientific article; zbMATH DE number 139903 (Why is no real title available?)
• Succinct Certificates for Almost All Subset Sum Problems
• scientific article; zbMATH DE number 1315279 (Why is no real title available?)
• On a subset sum algorithm and its probabilistic and other applications
• Dense subset sum may be the hardest
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• An Average-Case Sublinear Exact Li and Stephens Forward Algorithm
• Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum
• STACS 2005
• Fast exact and approximate algorithms for k-partition and scheduling independent tasks

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 Q4036607)