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

DOI10.1016/j.disopt.2010.03.004zbMath1241.90176MaRDI 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 path; approximation; minimum spanning tree; knapsack; min-max; fptas; min-max regret; minimum weighted perfect matching

Mathematics Subject Classification ID

90C47: Minimax problems in mathematical programming

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Related Items

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

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