An approximation algorithm for interval data minmax regret combinatorial optimization problems

被引：92

作者：

Kasperski, A

Zielinski, P

机构：

[1] Wroclaw Tech Univ, Inst Math & Comp Sci, PL-50370 Wroclaw, Poland

[2] Wroclaw Tech Univ, Inst Ind Engn & Management, PL-50370 Wroclaw, Poland

来源：

INFORMATION PROCESSING LETTERS | 2006年 / 97卷 / 05期

关键词：

robust optimization; maximal regret; approximation algorithms; combinatorial optimization;

D O I：

10.1016/j.ipl.2005.11.001

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The general problem of minimizing the maximal regret in combinatorial optimization problems with interval data is considered. In many cases, the minmax regret versions of the classical, polynomially solvable, combinatorial optimization problems become NP-hard and no approximation algorithms for them have been known. Our main result is a polynomial time approximation algorithm with a performance ratio of 2 for this class of problems. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：177 / 180

页数：4

共 11 条

[1]

ARON I, 2002, P 18 C UNC ART INT E

[2] On the complexity of the robust spanning tree problem with interval data [J].