Finding weighted MAXCUT in a graph with uncertain weights

The uncertainty theory from the viewpoint of Liu is a new way to deal with problems which some of parameters are not determinate. Especially, this theory is based on experts beliefs and by introducing a measure in these beliefs tries to overcome to uncertainty.One of the most important classic combinatorial optimization problem is finding a maximum cut for a graph. It has wide range of application such as scheduling. It is proved that this is an NP-hard problem and for arbitrary graph, there are only approximate algorithms. In this paper, we investigate this problem with indeterministic weights and obtain an equivalent deterministic integer programming model. Considering the concept of uncertainty distribution of an uncertain variable, two different models are constructed. The first modelconsiders α-chance method and the second exploits the expected value of the uncertain variables. Both models areconverted to deterministic ones.

کلیدواژه ها:

Maximum Cut ، Integer Programming ، Uncertainty Theory.