The present work tackles a recent problem in the class of cardinality constrained combinatorial optimization problems for the planar graph case: the minimum k-cardinality cut problem. Given an undirected edge-weighted connected graph the min k-cardinality cut problem consists in finding a partition of the vertex set V in two sets V-1, V-2 such that the number of the edges between V-1 and V-2 is exactly k and the sum of the weights of these edges is minimal. Although for general graphs the problem is already strongly NP-hard, we have found a pseudopolynomial algorithm for the planar graph case. This algorithm is based on the fact that the min k-cardinality cut problem in the original graph is equivalent to a bi-weighted exact perfect matching problem in a suitable transformation of the geometric dual graph. Because the Lagrangian relaxation of cardinality constraint yields a max cut problem and max cut is polynomially solvable in planar graphs, we also develop a Lagrangian heuristic for the min k-cardinality cut in planar graphs. We compare the performance of this heuristic with the performance of a more general heuristic based on a Semidefinite Programming relaxation and on the Goemans and Williamson's random hyperplane technique. (C) 2006 Wiley Periodicals, Inc.
Solving minimum k-cardinality cut problems in planar graphs / M. BRUGLIERI, F. MAFFIOLI, M. TRUBIAN. - In: NETWORKS. - ISSN 0028-3045. - 48:4(2006), pp. 195-208. [10.1002/net.20129]
Solving minimum k-cardinality cut problems in planar graphs
M. TrubianUltimo
2006
Abstract
The present work tackles a recent problem in the class of cardinality constrained combinatorial optimization problems for the planar graph case: the minimum k-cardinality cut problem. Given an undirected edge-weighted connected graph the min k-cardinality cut problem consists in finding a partition of the vertex set V in two sets V-1, V-2 such that the number of the edges between V-1 and V-2 is exactly k and the sum of the weights of these edges is minimal. Although for general graphs the problem is already strongly NP-hard, we have found a pseudopolynomial algorithm for the planar graph case. This algorithm is based on the fact that the min k-cardinality cut problem in the original graph is equivalent to a bi-weighted exact perfect matching problem in a suitable transformation of the geometric dual graph. Because the Lagrangian relaxation of cardinality constraint yields a max cut problem and max cut is polynomially solvable in planar graphs, we also develop a Lagrangian heuristic for the min k-cardinality cut in planar graphs. We compare the performance of this heuristic with the performance of a more general heuristic based on a Semidefinite Programming relaxation and on the Goemans and Williamson's random hyperplane technique. (C) 2006 Wiley Periodicals, Inc.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.