Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach

DOI10.1007/978-3-540-69311-6_31zbMath1143.90385OpenAlexW1484072583MaRDI QIDQ3507347

Changlin Wan, Zhongzhi Shi

Publication date: 19 June 2008

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69311-6_31

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• A new enumeration scheme for the knapsack problem
• Improved low-density subset sum algorithms
• Solving dense subset-sum problems by using analytical number theory
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• Where are the hard knapsack problems?
• Phase transition and finite-size scaling for the integer partitioning problem
• Discrete Dynamic Programming and Capital Allocation
• Number partitioning as a random energy model
• On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem
• Solving low-density subset sum problems
• An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem
• Computing Partitions with Applications to the Knapsack Problem
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Statistical mechanics of an NP-complete problem: subset sum
• STACS 2005
• Random knapsack in expected polynomial time
• An exact algorithm for the subset sum problem

This page was built for publication: Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach