On the complexity of a class of combinatorial optimization problems with uncertainty
From MaRDI portal
One way of dealing with combinatorial optimization problems with uncertainty in the input data is a worst case approach: one is looking for a solution that performs well for all scenarios. The minimax regret (or robust) version of the worst case approach minimizes the worst case loss in the objective function which occurs since one does not know which scenario will take place. There are two ways to represent scenarios: either a finite set of scenarios is given explicitly by listing the corresponding values of the parameters or an interval of uncertainty is specified for each parameter. The authors show that the robust version of finding a minimum weight base in a uniform matroid is NP-hard in the case the scenarios are represented explicitly by a finite set, but polynomially solvable in the case of an interval representation of the scenarios. Let the uniform matroid of rank \(p\) be defined on a ground set of cardinality \(m\) and let intervals for the weights be given. For this case the author states an \(O((\min (p, m-p))^2m)\) algorithm for finding a robust solution.
Recommendations
- Minmax regret combinatorial optimization problems: an algorithmic perspective
- Short paper -- A note on robust combinatorial optimization with generalized interval uncertainty
- Minmax regret bottleneck problems with solution-induced interval uncertainty structure
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- On the complexity of minmax regret linear programming
Cited in
(92)- Some tractable instances of interval data minmax regret problems
- Combinatorial optimization under uncertainty
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- Computing and minimizing the relative regret in combinatorial optimization with interval data
- Choosing robust solutions in discrete optimization problems with fuzzy costs
- Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights
- An approximation algorithm for interval data minmax regret combinatorial optimization problems
- Improved polynomial algorithms for robust bottleneck problems with interval data
- Minmax regret linear resource allocation problems.
- A minimum expected regret model for the shortest path problem with solution-dependent probability distributions
- A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs
- Robust scheduling to minimize the weighted number of late jobs with interval due-date uncertainty
- On recoverable and two-stage robust selection problems with budgeted uncertainty
- Minmax regret combinatorial optimization problems with ellipsoidal uncertainty sets
- Robust location of new housing developments using a choice model
- Ordered weighted average optimization in multiobjective spanning tree problem
- Robust optimization analysis for multiple attribute decision making problems with imprecise information
- Facility location problems with uncertainty on the plane
- Distributionally robust discrete optimization with entropic Value-at-Risk
- Interval data minmax regret network optimization problems
- On the complexity of minmax regret linear programming
- Min-max and min-max (relative) regret approaches to representatives selection problem
- Complexity of the robust weighted independent set problems on interval graphs
- Robust two-stage combinatorial optimization problems under convex second-stage cost 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
- Complexity results and exact algorithms for robust knapsack problems
- A randomized algorithm for the min-Max selecting items problem with uncertain weights
- Robust min-max regret scheduling to minimize the weighted number of late jobs with interval processing times
- Controlling risk and demand ambiguity in newsvendor models
- Robust recoverable and two-stage selection problems
- Complexity results for common due date scheduling problems with interval data and minmax regret criterion
- Robust recoverable 0-1 optimization problems under polyhedral uncertainty
- Complexity of minimizing the total flow time with interval data and minmax regret criterion
- Robust maximum weighted independent-set problems on interval graphs
- A note on the Bertsimas \& Sim algorithm for robust combinatorial optimization problems
- Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion
- Scenario relaxation algorithm for finite scenario-based min-max regret and min-max relative regret robust optimization
- Strong formulations of robust mixed 0-1 programming
- A Benders decomposition approach for the robust spanning tree problem with interval data
- The minmax regret permutation flow-shop problem with two jobs
- Minmax regret maximal covering location problems with edge demands
- Combinatorial optimization problems with balanced regret
- Single machine scheduling problems with uncertain parameters and the OWA criterion
- On the finite optimal convergence of logic-based Benders' decomposition in solving 0-1 min-max regret optimization problems with interval costs
- On the complexity of nonoverlapping multivariate marginal bounds for probabilistic combinatorial optimization problems
- The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows
- Probabilistic models for the Steiner tree problem
- Optimization under Uncertainty via CometBoards
- Solving linear unconstrained problems of combinatorial optimization on arrangements under stochastic uncertainty
- Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem
- A Relative Robust Optimization Approach for Full Factorial Scenario Design of Data Uncertainty and Ambiguity
- On discrete optimization with ordering
- New models for the robust shortest path problem: complexity, resolution and generalization
- The robust set covering problem with interval data
- Approximation with a fixed number of solutions of some multiobjective maximization problems
- Two-stage minimax regret robust uncapacitated lot-sizing problems with demand uncertainty
- Minmax regret bottleneck problems with solution-induced interval uncertainty structure
- Approximating a two-machine flow shop scheduling under discrete scenario uncertainty
- Combinatorial optimization problems with uncertain costs and the OWA criterion
- Constrained shortest path with uncertain transit times
- scientific article; zbMATH DE number 7075885 (Why is no real title available?)
- The Minimum Cost Query Problem on Matroids with Uncertainty Areas.
- Robust mean absolute deviation problems on networks with linear vertex weights
- Scheduling with uncertainties on new computing platforms
- Towards a robust scheduling on unrelated parallel machines: a scenarios based approach
- On a Class of Interval Data Minmax Regret CO Problems
- Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality
- The computational complexity of the relative robust shortest path problem with interval data
- Robust Algorithms for TSP and Steiner Tree
- Optimal scenario reduction for one- and two-stage robust optimization with discrete uncertainty in the objective
- Modeling the Emergency Service Network of Police Special Forces Units for High-Risk Law Enforcement Operations
- Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty
- Exact and heuristic algorithms for the interval data robust assignment problem
- Benchmarking problems for robust discrete optimization
- Almost robust discrete optimization
- Robust algorithms for TSP and Steiner tree
- The robust vehicle routing problem with synchronization: models and branch-and-cut algorithms
- Robust combinatorial optimization problems under budgeted interdiction uncertainty
- Robust resource allocations in temporal networks
- Optimization-based computation and integration of ordered measures
- Robust approach to restricted items selection problem
- On combinatorial optimization problems on matroids with uncertain weights
- Minmax regret location--allocation problem on a network under uncertainty
- Restricted robust uniform matroid maximization under interval uncertainty
- Minimax regret spanning arborescences under uncertain costs
- Approximation and resolution of min-max and min-max regret versions of combinatorial optimization problems. (Abstract of Thesis)
- Using the WOWA operator in robust discrete optimization problems
- Min-max regret robust optimization approach on interval data uncertainty
- Minimizing total weighted flow time of a set of jobs with interval processing times
- On the approximability of minmax (regret) network optimization problems
This page was built for publication: On the complexity of a class of combinatorial optimization problems with uncertainty
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5935709)
