Robust recoverable and two-stage selection problems
From MaRDI portal
Publication:2410249
Abstract: In this paper the following selection problem is discussed. A set of items is given and we wish to choose a subset of exactly items of the minimum total cost. This problem is a special case of 0-1 knapsack in which all the item weights are equal to~1. Its deterministic version has a trivial -time algorithm, which consists in choosing items of the smallest costs. In this paper it is assumed that the item costs are uncertain. Two robust models, namely two-stage and recoverable ones, under discrete and interval uncertainty representations, are discussed. Several positive and negative complexity results for both of them are provided.
Recommendations
- On recoverable and two-stage robust selection problems with budgeted uncertainty
- A linear time algorithm for the robust recoverable selection problem
- Recoverable Robust Combinatorial Optimization Problems
- Recoverable robust representatives selection problems with discrete budgeted uncertainty
- Robust approach to restricted items selection problem
- Complexity and in-approximability of a selection problem in robust optimization
- Two selection problems revisited
- Efficient solution selection for two-stage stochastic programs
- Decomposition approaches for recoverable robust optimization problems
Cites work
- A randomized algorithm for the min-Max selecting items problem with uncertain weights
- An improved algorithm for selecting \(p\) items with uncertain returns according to the minmax-regret criterion
- Approximability of the two-stage stochastic knapsack problem with discretely distributed weights
- Approximating the min-max (regret) selecting items problem
- Commitment under uncertainty: Two-stage stochastic matching problems
- scientific article; zbMATH DE number 5542185 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1219584 (Why is no real title available?)
- scientific article; zbMATH DE number 544186 (Why is no real title available?)
- scientific article; zbMATH DE number 1559563 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- scientific article; zbMATH DE number 3185974 (Why is no real title available?)
- Improved approximation algorithms for the Min-Max selecting items problem
- Lagrangean decomposition for mean-variance combinatorial optimization
- Network flows. Theory, algorithms, and applications.
- On the approximability of robust spanning tree problems
- On the complexity of a class of combinatorial optimization problems with uncertainty
- On the recoverable robust traveling salesman problem
- On two-stage stochastic knapsack problems
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- Recoverable robust knapsacks: the discrete scenario case
- Recoverable robust shortest path problems
- Recoverable robust spanning tree problem under interval uncertainty representations
- Robust discrete optimization and its applications
- Robust discrete optimization and network flows
- Stochastic maximum weight forest problem
- The concept of recoverable robustness, linear programming recovery, and railway applications
- Two-stage stochastic matching and spanning tree problems: polynomial instances and approximation
Cited in
(30)- Two-stage flexible-choice problems under uncertainty
- Sensitivity and robustness in selection problems.
- On recoverable and two-stage robust selection problems with budgeted uncertainty
- A biobjective approach to recoverable robustness based on location planning
- A linear time algorithm for the robust recoverable selection problem
- Decision space robustness for multi-objective integer linear programming
- Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty
- Flexible here-and-now decisions for two-stage multi-objective optimization: method and application to energy system design selection
- Two-stage robust optimization problems with two-stage uncertainty
- A parameterized view to the robust recoverable base problem of matroids under structural uncertainty
- Recoverable robust representatives selection problems with discrete budgeted uncertainty
- Combinatorial two-stage minmax regret problems under interval uncertainty
- A randomized algorithm for the min-Max selecting items problem with uncertain weights
- Two-stage combinatorial optimization problems under risk
- Robust recoverable 0-1 optimization problems under polyhedral uncertainty
- Combinatorial optimization problems with balanced regret
- The minimum expectation selection problem
- Mid-term capacity redeployment of Rescue Centers under simultaneous requirements
- Optimal scenario reduction for one- and two-stage robust optimization with discrete uncertainty in the objective
- A single representative min-max-min robust selection problem with alternatives and budgeted uncertainty
- On the complexity of robust multi-stage problems with discrete recourse
- Benchmarking problems for robust discrete optimization
- Recoverable robust shortest path problem under interval budgeted uncertainty representations
- Robust combinatorial optimization under convex and discrete cost uncertainty
- The robust selection problem with information discovery
- Completeness in the polynomial hierarchy for many natural problems in bilevel and robust optimization
- On the complexity of recoverable robust optimization in the polynomial hierarchy
- Multi-stage selection under bounded variation
- Robust approach to restricted items selection problem
- Investigating the recoverable robust single machine scheduling problem under interval uncertainty
This page was built for publication: Robust recoverable and two-stage selection problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2410249)
