Academic
Publications
Linear and quadratic programming approaches for the general graph partitioning problem

Linear and quadratic programming approaches for the general graph partitioning problem,10.1007/s10898-009-9520-1,Journal of Global Optimization,Neng F

Linear and quadratic programming approaches for the general graph partitioning problem   (Citations: 6)
BibTex | RIS | RefWorks Download
The graph partitioning problem is to partition the vertex set of a graph into a number of nonempty subsets so that the total weight of edges connecting distinct subsets is minimized. Previous research requires the input of cardinalities of subsets or the number of subsets for equipartition. In this paper, the problem is formulated as a zero-one quadratic programming problem without the input of cardinalities. We also present three equivalent zero-one linear integer programming reformulations. Because of its importance in data biclustering, the bipartite graph partitioning is also studied. Several new methods to determine the number of subsets and the cardinalities are presented for practical applications. In addition, hierarchy partitioning and partitioning of bipartite graphs without reordering one vertex set, are studied.
Journal: Journal of Global Optimization , vol. 48, no. 1, pp. 57-71, 2010
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...The graph partitioning problem has been studied for a long time and recently studied by linear and quadratic programming approaches [6]...
    • ...given cardinalities nk(k = 1, ··· , K). For general graph partitioning [6], nk is not necessarily to be given and only required to satisfy nk > 1; For equal partitioning, nk ∈ {� N/K� , � N/K� + 1} with total ∑k nk = N. In CNP, we also delete exactly K vertices to minimize the pairwise connectivity between the remaining vertices...
    • ...In graph partitioning, the paper [6] has discussed how to obtain K and presented that the cardinalities n1, ··· , nK can be relaxed to an interval region [Cmin,Cmax]...

    Neng Fanet al. Robust Optimization of Graph Partitioning and Critical Node Detection ...

    • ...For minimum cut (Definition 5) of graph partitioning, the determination of K is studied in Fan and Pardalos (2010) by introducing a penalty function...
    • ...For minimum cut (Definition 5) of graph partitioning, the cardinalities are always chosen as equals N/K (Karisch and Rendl 1998; Lisser and Rendl 2003), pre-given integers (Wolkowicz and Zhao 1996; Hager and Krylyuk 2002) or values in a range (Fan and Pardalos 2010)...
    • ...titioning by minimum cut (Fan and Pardalos 2010)...
    • ...The graph partitioning requiring the given cardinalities n1 ,...,n K can be solved by the approaches of linear programming (Lisser and Rendl 2003; Fan and Pardalos 2010), quadratic programming (Fan and Pardalos 2010; Hager and Krylyuk 2002) and semidefinite programming (Lisser and Rendl 2003; Karisch and Rendl 1998; Wolkowicz and Zhao 1996)...
    • ...The graph partitioning requiring the given cardinalities n1 ,...,n K can be solved by the approaches of linear programming (Lisser and Rendl 2003; Fan and Pardalos 2010), quadratic programming (Fan and Pardalos 2010; Hager and Krylyuk 2002) and semidefinite programming (Lisser and Rendl 2003; Karisch and Rendl 1998; Wolkowicz and Zhao 1996)...
    • ...In practice, the antidegeneracy constraints (Fan and Pardalos 2010) are always added to reduce the computational time...

    Neng Fanet al. Multi-way clustering and biclustering by the Ratio cut and Normalized ...

    • ...For K biclusters, Dhillon [17] used k-means algorithm [31, 57] after obtaining the indicator vector y, and another direct approach is from [23] by defining an indicator matrix...

    Neng Fanet al. Recent Advances of Data Biclustering with Application in Computational...

    • ...For more information about alternative clustering approaches, see Tan et al. (2007), Fan and Pardalos (2010)...

    Flor A. Espinozaet al. Using Hierarchical Clustering and Dendrograms to Quantify the Clusteri...

    • ...Usually, K is chosen from {2, ··· , N − 1} .A s shown in [3,4], the size nk for subset k can be loosely chosen in a range...
    • ...As stated in [3,5], many mathematical programming methods, including linear programming, quadratic programming, and semidefinite programming, are used for this problem...
    • ...All generated weights satisfy w ij , c s ∈ [2, 3] for (vi, v j) ∈ E. The number N(N − 1)r/2 of decision variables y ij s is related to the number of edges, which is related to N, r; the number N(N − 1)rS/ 2o fz s s is determined by N, r, s; and the number N · K · S of x s s is determined N, S, K. In Theorem 2, the variables u s k s are introduced, and the number of u s k s is N(N − 1)rKS/2...

    Neng Fanet al. On the Two-Stage Stochastic Graph Partitioning Problem

Sort by: