A relaxed FPTAS for chance-constrained knapsack

DOI10.4230/LIPICS.ISAAC.2018.72MaRDI QIDQ5091069FDOQ5091069

Authors: Galia Shabtai, Danny Raz, Yuval Shavitt 

Publication date: 21 July 2022

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

zbMATH Keywords

combinatorial optimizationapproximation algorithmsstochastic knapsackchance constraint

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

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

Cited In (3)

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

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)