Approximating Min-Max (Regret) Versions of Some Polynomial Problems

DOI10.1007/11809678_45zbMath1162.90536MaRDI QIDQ3591305

Hassene Aissi, Daniel Vanderpooten, Cristina Bazgan

Publication date: 10 September 2007

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/5871

zbMATH Keywords

shortest path; approximation; minimum spanning tree; min-max; fptas; min-max regret

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

68W25: Approximation algorithms

Related Items

Robust Postdonation Blood Screening Under Prevalence Rate Uncertainty, An Exact Algorithm for Large-Scale Continuous Nonlinear Resource Allocation Problems with Minimax Regret Objectives, A study on several combination problems of classic shop scheduling and shortest path, Maximizing the minimum voter satisfaction on spanning trees, On the approximability of minmax (regret) network optimization problems, A note on maximizing the minimum voter satisfaction on spanning trees, Min-max and min-max regret versions of combinatorial optimization problems: A survey, Reference points and approximation algorithms in multicriteria discrete optimization, Exact algorithms for OWA-optimization in multiobjective spanning tree problems, A randomized algorithm for the min-Max selecting items problem with uncertain weights, A combination of flow shop scheduling and the shortest path problem, Combinations of Some Shop Scheduling Problems and the Shortest Path Problem: Complexity and Approximation Algorithms, Approximating Single Machine Scheduling with Scenarios