On the complexity of a class of combinatorial optimization problems with uncertainty (Q5935709): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Normalize DOI.
Property / DOI
 
Property / DOI: 10.1007/s101070100216 / rank
Normal rank
 
Property / DOI
 
Property / DOI: 10.1007/S101070100216 / rank
 
Normal rank

Revision as of 14:41, 8 December 2024

scientific article; zbMATH DE number 1610919
Language Label Description Also known as
English
On the complexity of a class of combinatorial optimization problems with uncertainty
scientific article; zbMATH DE number 1610919

    Statements

    On the complexity of a class of combinatorial optimization problems with uncertainty (English)
    0 references
    0 references
    28 February 2002
    0 references
    One way of dealing with combinatorial optimization problems with uncertainty in the input data is a worst case approach: one is looking for a solution that performs well for all scenarios. The minimax regret (or robust) version of the worst case approach minimizes the worst case loss in the objective function which occurs since one does not know which scenario will take place. There are two ways to represent scenarios: either a finite set of scenarios is given explicitly by listing the corresponding values of the parameters or an interval of uncertainty is specified for each parameter. The authors show that the robust version of finding a minimum weight base in a uniform matroid is NP-hard in the case the scenarios are represented explicitly by a finite set, but polynomially solvable in the case of an interval representation of the scenarios. Let the uniform matroid of rank \(p\) be defined on a ground set of cardinality \(m\) and let intervals for the weights be given. For this case the author states an \(O((\min (p, m-p))^2m)\) algorithm for finding a robust solution.
    0 references
    robust optimization
    0 references
    minmax regret
    0 references
    computational complexity
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references