Stochastic analysis of greedy algorithms for the subset sum problem

DOI10.1246/CL.2007.732zbMATH Open0941.90064OpenAlexW2951146621MaRDI QIDQ1806779FDOQ1806779

Ulrich Pferschy

Publication date: 8 November 1999

Published in: CEJOR. Central European Journal of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1246/cl.2007.732

Recommendations

• The probabilistic analysis of a greedy satisfiability algorithm
• scientific article; zbMATH DE number 1947423
• scientific article; zbMATH DE number 1086990
• scientific article; zbMATH DE number 1058053
• On the analysis of stochastic divide and conquer algorithms
• The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem
• Publication:4724418
• scientific article
• A refined analysis of submodular greedy
• On the power of random greedy algorithms

zbMATH Keywords

probabilistic analysissubset sum problemexpected solution value

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Combinatorial probability (60C05)

Cited In (4)

• Average-case performance analysis of an approximation algorithm for maximum subset sum using recurrence relations
• Priority Algorithms for the Subset-Sum Problem
• The bounded subset sum problem is almost everywhere randomly decidable in O(n)
• Average-case performance of rollout algorithms for knapsack problems

This page was built for publication: Stochastic analysis of greedy algorithms for the subset sum problem

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