A novel algorithmic approach is presented for the problem of partitioning a connected undirected weighted graph under constraints such as cardinality or membership requirements or must-link and cannot-link constraints. Such constrained problems can be NP-hard combinatorial optimization problems. They are restated as matrix nearness problems for the weight matrix of the graph, where the objective is to minimize the distance between the given weight matrix and perturbed weight matrices for which a functional of an eigenvalue and eigenvector of the graph Laplacian takes its minimal value. A key element in the numerical solution of these matrix nearness problems is the use of a gradient system of matrix differential equations for the functional.
Constrained graph partitioning via matrix differential equations
Guglielmi N.;
2019-01-01
Abstract
A novel algorithmic approach is presented for the problem of partitioning a connected undirected weighted graph under constraints such as cardinality or membership requirements or must-link and cannot-link constraints. Such constrained problems can be NP-hard combinatorial optimization problems. They are restated as matrix nearness problems for the weight matrix of the graph, where the objective is to minimize the distance between the given weight matrix and perturbed weight matrices for which a functional of an eigenvalue and eigenvector of the graph Laplacian takes its minimal value. A key element in the numerical solution of these matrix nearness problems is the use of a gradient system of matrix differential equations for the functional.File | Dimensione | Formato | |
---|---|---|---|
2019_SIAMJMatrixAnalAppl_40_Andreotti.pdf
non disponibili
Tipologia:
Altro materiale allegato
Licenza:
Non pubblico
Dimensione
2.51 MB
Formato
Adobe PDF
|
2.51 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.