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

DOI10.1007/11809678_45zbMath1162.90536OpenAlexW2124833419MaRDI 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 pathapproximationminimum spanning treemin-maxfptasmin-max regret

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (13)

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

This page was built for publication: Approximating Min-Max (Regret) Versions of Some Polynomial Problems