Robust approach to restricted items selection problem
From MaRDI portal
Abstract: We consider the robust version of items selection problem, in which the goal is to choose representatives from a family of sets, preserving constraints on the allowed items' combinations. We prove NP-hardness of the deterministic version, and establish polynomially solvable special cases. Next, we consider the robust version in which we aim at minimizing the maximum regret of the solution under interval parameter uncertainty. We show that this problem is hard for the second level of polynomial-time hierarchy. We develop an exact solution algorithm for the robust problem, based on cut generation, and present the results of computational experiments.
Recommendations
- Robust recoverable and two-stage selection problems
- Restricted robust uniform matroid maximization under interval uncertainty
- On recoverable and two-stage robust selection problems with budgeted uncertainty
- Approximating the min-max (regret) selecting items problem
- Complexity and in-approximability of a selection problem in robust optimization
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1234104 (Why is no real title available?)
- scientific article; zbMATH DE number 663895 (Why is no real title available?)
- An improved algorithm for selecting \(p\) items with uncertain returns according to the minmax-regret criterion
- Approximability of the robust representatives selection problem
- Complexity and in-approximability of a selection problem in robust optimization
- Complexity of interval minmax regret scheduling on parallel identical machines with total completion time criterion
- Complexity of the min-max and min-max regret assignment problems
- Discrete optimization with interval data. Minmax regret and fuzzy approach
- Exact and heuristic algorithms for the interval data robust assignment problem
- Interval data minmax regret network optimization problems
- Min-max and min-max (relative) regret approaches to representatives selection problem
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- On the complexity of a class of combinatorial optimization problems with uncertainty
- Robust discrete optimization and network flows
- Robust scheduling to minimize the weighted number of late jobs with interval due-date uncertainty
- Robust solutions of uncertain linear programs
- Robustness in operational research and decision aiding: a multi-faceted issue
- The Price of Robustness
- The concept of recoverable robustness, linear programming recovery, and railway applications
- The polynomial-time hierarchy
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
Cited in
(6)- A linear time algorithm for the robust recoverable selection problem
- Restricted robust uniform matroid maximization under interval uncertainty
- Approximability of the robust representatives selection problem
- Robust recoverable and two-stage selection problems
- Robustly assigning unstable items
- On recoverable and two-stage robust selection problems with budgeted uncertainty
This page was built for publication: Robust approach to restricted items selection problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q828685)
