Some tractable instances of interval data minmax regret problems

被引：5

作者：

Escoffier, Bruno ^{[1
]}

Monnot, Jerome ^{[1
]}

Spanjaard, Olivier ^{[2
]}

机构：

[1] Univ Paris 09, LAMSADE, CNRS, F-75775 Paris 16, France

[2] Univ Paris 06, LIP6, F-75252 Paris, France

来源：

OPERATIONS RESEARCH LETTERS | 2008年 / 36卷 / 04期

关键词：

robust optimization; interval data; shortest path; spanning tree; bipartite perfect matching;

D O I：

10.1016/j.orl.2007.12.004

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we provide polynomial and pseudopolynomial algorithms for classes of particular instances of interval data minmax regret graph problems. These classes are defined using a parameter that measures the distance from well-known solvable instances. Tractable cases occur when the parameter is bounded by a constant. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：424 / 429

页数：6

共 18 条

[1]

[Anonymous], PARAMETERIZED COMPLE

[2]

[Anonymous], 2001, ROBUST SHORTEST PATH

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

Aron, ID ;

Van Hentenryck, P .

OPERATIONS RESEARCH LETTERS, 2004, 32 (01) :36-40

[4]

ATSERIAS A, 2006, DIGRAPH COLORING PRO

[5] Interval data minmax regret network optimization problems [J].

Averbakh, I ;

Lebedev, V .

DISCRETE APPLIED MATHEMATICS, 2004, 138 (03) :289-301

[6] On the complexity of a class of combinatorial optimization problems with uncertainty [J].

Averbakh, I .

MATHEMATICAL PROGRAMMING, 2001, 90 (02) :263-272

[7] OPTIMAL REDUCTION OF 2-TERMINAL DIRECTED ACYCLIC GRAPHS [J].

BEIN, WW ;

KAMBUROWSKI, J ;

STALLMANN, MFM .

SIAM JOURNAL ON COMPUTING, 1992, 21 (06) :1112-1129

[8]

Bertele U, 1972, NONSERIAL DYNAMIC PR

[9] A linear-time ie algorithm for finding three-decompositions of small treewidth [J].

Bodlaender, HL .

SIAM JOURNAL ON COMPUTING, 1996, 25 (06) :1305-1317

[10]

ESCOFFIER B, 2008, LECT NOTES COMPUTER, V4910

← 1 2 →