×

A 2-approximation for minmax regret problems via a mid-point scenario optimal solution. (English) Zbl 1197.90337

Summary: A 2-approximation method for minmax regret optimization problems is developed which extends the work of A. Kasperski and P. Zielinski [Inf. Process. Lett. 97, No. 5, 177–180 (2006; Zbl 1184.68640)] from finite to compact constraint sets.

MSC:

90C47 Minimax problems in mathematical programming
90C59 Approximation methods and heuristics in mathematical programming

Citations:

Zbl 1184.68640
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aissi, H.; Bazgan, C.; Vanderpooten, D., Min-max and min-max regret versions of combinatorial optimization problems: a survey, European Journal of Operational Research, 197, 2, 427-438 (2009) · Zbl 1159.90472
[2] Averbakh, I., Complexity of robust single facility location problems on networks with uncertain edge lengths, Discrete Applied Mathematics, 127, 505-522 (2003) · Zbl 1038.90041
[3] Averbakh, I.; Lebedev, V., On the complexity of minmax regret linear programming, European Journal of Operational Research, 160, 227-231 (2005) · Zbl 1067.90132
[4] Daniels, R. L.; Kouvelis, P., Robust scheduling to hedge against processing time uncertainty in single-stage production, Management Science, 41, 2, 363-376 (1995) · Zbl 0832.90050
[5] Kasperski, A.; Zieliński, P., An approximation algorithm for interval data minmax regret combinatorial optimization problems, Information Processing Letters, 97, 177-180 (2006) · Zbl 1184.68640
[6] Kasperski, A.; Zieliński, P., A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion, Operations Research Letters, 36, 3, 343-344 (2008) · Zbl 1151.90417
[7] Kouvelis, P.; Yu, G., Robust Discrete Optimization and its Applications (1997), Kluwer Academic Publisher: Kluwer Academic Publisher Boston · Zbl 0873.90071
[8] Mausser, H. E.; Laguna, M., Heuristic to minimax absolute regret for linear programs with interval objective function coefficients, European Journal of Operational Research, 117, 1, 157-174 (1999) · Zbl 0998.90058
[9] Rockafellar, R. T., Convex Analysis (1972), Princeton University Press: Princeton University Press New Jersey · Zbl 0224.49003
[10] Zielinski, P., The computational complexity of the relative robust shortest path problem with interval data, European Journal of Operational Research, 158, 3, 570-576 (2004) · Zbl 1056.90125
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.