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

DOI10.1016/J.EJOR.2012.01.005zbMATH Open1244.90241OpenAlexW1966509452MaRDI QIDQ439704FDOQ439704

Authors: E. 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

Recommendations

• A 2-approximation for minmax regret problems via a mid-point scenario optimal solution
• A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem
• Minmax regret solutions for minimax optimization problems with uncertainty
• Min max min robust (relative) regret combinatorial optimization
• Minmax regret combinatorial optimization problems: an algorithmic perspective

zbMATH Keywords

robustness and sensitivity analysisconstant factor approximationminmax-regret models

Mathematics Subject Classification ID

Sensitivity, stability, parametric optimization (90C31) Minimax problems in mathematical programming (90C47)

Cites Work

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

Cited In (15)

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

This page was built for publication: On a constant factor approximation for minmax regret problems using a symmetry point scenario

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q439704)