Approximating the stochastic Knapsack problem: the benefit of adaptivity
From MaRDI portal
Recommendations
- Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem
- The benefit of adaptivity in the stochastic knapsack problem with dependence on the state of nature
- Adaptivity in the stochastic blackjack knapsack problem
- Improved approximation results for stochastic knapsack problems
- Adaptivity and approximation for stochastic packing problems
Cited in
(92)- Column generation strategies and decomposition approaches for the two-stage stochastic multiple knapsack problem
- A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs
- \(K\)-adaptability in stochastic combinatorial optimization under objective uncertainty
- Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem
- Improved bounds in stochastic matching and optimization
- Maximizing expected utility over a knapsack constraint
- Queue-constrained packing: a vehicle ferry case study
- Stage-\(t\) scenario dominance for risk-averse multi-stage stochastic mixed-integer programs
- Improved online algorithm for fractional knapsack in the random order model
- Strongly polynomial FPTASes for monotone dynamic programs
- Dynamic node packing
- Exact algorithms for the 0-1 time-bomb knapsack problem
- Non-adaptive stochastic score classification and explainable halfspace evaluation
- Stochastic packing integer programs with few queries
- An adversarial model for scheduling with testing
- A column and constraint generation algorithm for the dynamic knapsack problem with stochastic item sizes
- Narrowing the search for optimal call-admission policies via a nonlinear stochastic knapsack model
- The benefit of adaptivity in the stochastic knapsack problem with dependence on the state of nature
- Approximability of the two-stage stochastic knapsack problem with discretely distributed weights
- An optimization model for web content adaptation
- Semi-infinite relaxations for the dynamic knapsack problem with stochastic item sizes
- Approximation algorithms for stochastic combinatorial optimization problems
- Adaptivity and approximation for stochastic packing problems
- Packing a knapsack of unknown capacity
- An adaptive stochastic knapsack problem
- The adaptive Knapsack problem with stochastic rewards
- Unrelated machine scheduling with stochastic processing times
- Submodular stochastic probing on matroids
- Improved approximation algorithms for stochastic matching
- Polymatroid Prophet Inequalities
- Ignorant vs. anonymous recommendations
- Stochastic Covering and Adaptivity
- Adaptivity in the stochastic blackjack knapsack problem
- The stochastic generalized bin packing problem
- Toward a model for backtracking and dynamic programming
- Approximation algorithms for stochastic and risk-averse optimization
- Boolean function analysis meets stochastic optimization: an approximation scheme for stochastic knapsack
- Relaxation analysis for the dynamic knapsack problem with stochastic item sizes
- Randomized algorithms for online knapsack problems
- The benefit of adaptivity in stochastic packing problems with probing
- Stochastic unsplittable flows
- A PTAS for a class of stochastic dynamic programs
- scientific article; zbMATH DE number 7626775 (Why is no real title available?)
- Stochastic knapsack revisited: the service level perspective
- The Risk-Averse Static Stochastic Knapsack Problem
- Stochastic graph exploration
- Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards
- Approximations to stochastic dynamic programs via information relaxation duality
- Ignorance is almost bliss: near-optimal stochastic matching with few queries
- Adaptive submodular ranking and routing
- Approximation algorithms for stochastic k-TSP
- Improvements and generalizations of stochastic knapsack and Markovian bandits approximation algorithms
- Maximizing expected utility for stochastic combinatorial optimization problems
- Submodular maximization with uncertain knapsack capacity
- Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
- A tight 2-approximation for preemptive stochastic scheduling
- Packing a knapsack of unknown capacity
- Improved approximation results for stochastic knapsack problems
- Note on a Class of Admission Control Policies for the Stochastic Knapsack Problem
- Stochastic combinatorial optimization via Poisson approximation
- scientific article; zbMATH DE number 7053373 (Why is no real title available?)
- Adaptive Bin Packing with Overflow
- scientific article; zbMATH DE number 7650393 (Why is no real title available?)
- On competitive recommendations
- Configuration balancing for stochastic requests
- Turnpikes in Finite Markov Decision Processes and Random Walk
- Stochastic graph exploration with limited resources
- Adaptivity gaps for the stochastic Boolean function evaluation problem
- Stochastic Probing with Increasing Precision
- Order-competitive ratio
- Sequential testing with subadditive costs
- A general framework for sequential batch-testing
- Replication and sequencing of unreliable jobs on m parallel machines: new results
- Approximation algorithms for correlated knapsack orienteering
- When LP is the cure for your matching woes: improved bounds for stochastic matchings
- Near-optimal algorithms for stochastic online bin packing
- Correlated stochastic knapsack with a submodular objective
- Model-based algorithms for the 0-1 time-bomb knapsack problem
- Online contention resolution schemes for size-stochastic knapsacks
- Configuration balancing for stochastic requests
- Stochastic set packing problem
- Improved approximation factor for adaptive influence maximization via simple greedy strategies
- Optimal composition ordering problems for piecewise linear functions
- Composition orderings for linear functions and matrix multiplication orderings
- Identifying approximate minimizers under stochastic uncertainity
- Non-adaptive evaluation of k-of-n functions: tight gap and a unit-cost PTAS
- Mixed-integer linear programming approximations for the stochastic knapsack
- Prioritized interdiction of nuclear smuggling via tabu search
- On the adaptivity gap of stochastic orienteering
- Robust execution strategies for project scheduling with unreliable resources and stochastic durations
- A PTAS for the chance-constrained knapsack problem with random item sizes
- Upper bounds for the 0-1 stochastic knapsack problem and a B\&B algorithm
This page was built for publication: Approximating the stochastic Knapsack problem: the benefit of adaptivity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3169009)
