?
Robust optimization of graph partitioning involving interval uncertainty
Задача разбиения графа заключается в разделении множества вершин графа на число непустых подмножеств так, чтобы общий вес ребер, соединяющих различные подмножества сводился к минимуму. Предшествующие исследования требуют ввода мощностей подмножеств или числа подмножеств для равнораспределения. В этой статье, проблема формулируется как Zero-one задача квадратичного программирования без ввода мощностей. Мы также представляем три формулировки равнозначного Zero-one линейного целого программирования. Из-за его важности в bi – кластеризации данных, разбиение двудольных графов также изучается. Для практического применения также описываются несколько новых методов определения числа подмножеств и мощности. Кроме того, изучается иерархия разделения и разбиения двудольных графов без переназначения одного множества вершин.