A relaxed FPTAS for chance-constrained knapsack

DOI10.4230/LIPICS.ISAAC.2018.72MaRDI QIDQ5091069zbMATH OpenFDO

Authors Galia Shabtai, Danny Raz, Yuval Shavitt

Publication date 21 July 2022

zbMATH Keywords

combinatorial optimizationapproximation algorithmsstochastic knapsackchance constraint

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• A PTAS for the chance-constrained knapsack problem with random item sizes
• Boolean function analysis meets stochastic optimization: an approximation scheme for stochastic knapsack
• Chance-Constrained Submodular Knapsack problem
• An FPTAS for stochastic unbounded min-knapsack problem
• Improved approximation results for stochastic knapsack problems

Cites work

• A PTAS for the chance-constrained knapsack problem with random item sizes
• Allocating Bandwidth for Bursty Connections
• Approximation algorithms for reliable stochastic combinatorial optimization
• Boolean function analysis meets stochastic optimization: an approximation scheme for stochastic knapsack
• Improved approximation results for stochastic knapsack problems
• Semi-infinite relaxations for the dynamic knapsack problem with stochastic item sizes
• Stochastic combinatorial optimization via Poisson approximation

Cited in

(4)

• An FPTAS for stochastic unbounded min-knapsack problem
• A PTAS for the chance-constrained knapsack problem with random item sizes
• Robust optimization-based heuristic algorithm for the chance-constrained knapsack problem using submodularity
• Minimizing the total tardiness and job rejection cost in a proportionate flow shop with generalized due dates

This page was built for publication: A relaxed FPTAS for chance-constrained knapsack

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