On a constant factor approximation for minmax regret problems using a symmetry point scenario

DOI10.1016/j.ejor.2012.01.005zbMath1244.90241MaRDI QIDQ439704

Eduardo Conde

Publication date: 16 August 2012

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2012.01.005

zbMATH Keywords

robustness and sensitivity analysis; constant factor approximation; minmax-regret models

Mathematics Subject Classification ID

90C47: Minimax problems in mathematical programming

90C31: Sensitivity, stability, parametric optimization

Related Items

Robust Algorithms for TSP and Steiner Tree, A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem, An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem, A minmax regret version of the time-dependent shortest path problem, Robust minmax regret combinatorial optimization problems with a resource-dependent uncertainty polyhedron of scenarios, A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs, Minmax regret combinatorial optimization problems with ellipsoidal uncertainty sets, On scenario aggregation to approximate robust combinatorial optimization problems, A single-machine scheduling problem with uncertainty in processing times and outsourcing costs, Minimizing maximum cost for a single machine under uncertainty of processing times, Representative scenario construction and preprocessing for robust combinatorial optimization problems, A robust optimization model for distribution network design under a mixed integer set of scenarios, Combinatorial optimization problems with balanced regret, The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows

Cites Work

• Unnamed Item
• The computational complexity of the relative robust shortest path problem with interval data
• A branch and bound algorithm for the robust spanning tree problem with interval data
• Complexity of the min-max and min-max regret assignment problems
• Using intervals for global sensitivity and worst-case analyses in multiattribute value trees
• Discrete optimization with interval data. Minmax regret and fuzzy approach
• A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion
• A 2-approximation for minmax regret problems via a mid-point scenario optimal solution
• Some tractable instances of interval data minmax regret problems
• A minmax regret approach to the critical path method with task interval times
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• Robust discrete optimization and its applications
• Minmax regret linear resource allocation problems.
• Complexity of robust single facility location problems on networks with uncertain edge lengths.
• A heuristic to minimax absolute regret for linear programs with interval objective function coefficients
• An exact algorithm for the robust shortest path problem with interval data
• On the complexity of minmax regret linear programming
• Complexity of minimizing the total flow time with interval data and minmax regret criterion
• A Benders decomposition approach for the robust spanning tree problem with interval data
• The robust shortest path problem with interval data via Benders decomposition
• An improved algorithm for the minmax regret median problem on a tree
• Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage Production
• The computational complexity of the criticality problems in a network with interval activity times