کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141707 957085 2008 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Complexity of the min–max (regret) versions of min cut problems
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
Complexity of the min–max (regret) versions of min cut problems
چکیده انگلیسی

This paper investigates the complexity of the min–max and min–max regret versions of the min s–ts–t cut and min cut problems. Even if the underlying problems are closely related and both polynomial, the complexities of their min–max and min–max regret versions, for a constant number of scenarios, are quite contrasted since they are respectively strongly NP-hard and polynomial. However, for a non-constant number of scenarios, these versions become strongly NP  -hard for both problems. In the interval scenario case, min–max versions are trivially polynomial. Moreover, for min–max regret versions, we obtain the same contrasted results as for a constant number of scenarios: min–max regret min s–ts–t cut is strongly NP-hard whereas min–max regret min cut is polynomial.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 5, Issue 1, February 2008, Pages 66–73
نویسندگان
, , ,