Stochastic analysis of greedy algorithms for the subset sum problem

DOI10.1246/CL.2007.732MaRDI QIDQ1806779zbMATHOpenAlexFDO

Authors 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

zbMATH Keywords

probabilistic analysissubset sum problemexpected solution value

Mathematics Subject Classification ID

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

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; zbMATH DE number 4057284
• A refined analysis of submodular greedy
• On the power of random greedy algorithms

Cited in

(5)

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

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)