General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems

DOI10.1016/j.disopt.2010.03.004zbMath1241.90176OpenAlexW2007863759MaRDI QIDQ429650

Hassene Aissi, Cristina Bazgan, Daniel Vanderpooten

Publication date: 20 June 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.03.004

zbMATH Keywords

shortest pathapproximationminimum spanning treeknapsackmin-maxfptasmin-max regretminimum weighted perfect matching

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (13)

Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem ⋮ Min‐Max quickest path problems ⋮ Proportional and maxmin fairness for the sensor location problem with chance constraints ⋮ Approximating combinatorial optimization problems with the ordered weighted averaging criterion ⋮ Min-max and min-max (relative) regret approaches to representatives selection problem ⋮ Using the WOWA operator in robust discrete optimization problems ⋮ Optimal scenario reduction for one- and two-stage robust optimization with discrete uncertainty in the objective ⋮ Approximating a two-machine flow shop scheduling under discrete scenario uncertainty ⋮ An improved genetic algorithm for single-machine inverse scheduling problem ⋮ Combinatorial optimization problems with uncertain costs and the OWA criterion ⋮ A unified approach to uncertain optimization ⋮ Complexity of the robust weighted independent set problems on interval graphs ⋮ Robust Discrete Optimization Problems with the WOWA Criterion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation of min-max and min-max regret versions of some combinatorial optimization problems
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• Exact arborescences, matchings and cycles
• Robust discrete optimization and its applications
• A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
• The combinatorial approach yields an NC algorithm for computing Pfaffians
• Approximation schemes for a class of subset selection problems
• Approximating Multiobjective Knapsack Problems
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Approximation Schemes for the Restricted Shortest Path Problem
• When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
• On the Max-Min 0-1 Knapsack Problem with Robust Optimization Applications
• Systems of distinct representatives and linear algebra

This page was built for publication: General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems