A Fast Approximation Algorithm For The Subset-Sum Problem

DOI10.1080/03155986.1994.11732245zbMath0823.90103OpenAlexW2395820029MaRDI QIDQ4313818

Eugene Levner, George Gens

Publication date: 29 November 1994

Published in: INFOR: Information Systems and Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/03155986.1994.11732245

zbMATH Keywords

knapsack problemNP-hardpolynomial approximation schemescaling methodsubset-sum-problem

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (2)

An optimization algorithm for the clearing of interbank payments ⋮ An efficient fully polynomial approximation scheme for the Subset-Sum problem.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear time randomizing algorithm for searching ranked functions
• Fast approximation algorithm for job sequencing with deadlines
• New scaling algorithms for the assignment and minimum mean cycle problems
• A note on 0.5-bounded greedy algorithms for the 0/1 knapsack problem
• A new saling algorithm for the maximum mean cut problem
• Approximate binary search algorithms for mean cuts and cycles
• Fast Approximation Algorithms for Knapsack Problems
• THE MULTIPLE-CHOICE KNAPSACK PROBLEM

This page was built for publication: A Fast Approximation Algorithm For The Subset-Sum Problem