𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Cardinality constrained minimum cut problems: complexity and algorithms

✍ Scribed by Maurizio Bruglieri; Francesco Maffioli; Matthias Ehrgott

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
377 KB
Volume
137
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

In several applications the solutions of combinatorial optimization problems (COP) are required to satisfy an additional cardinality constraint, that is to contain a ΓΏxed number of elements. So far the family of (COP) with cardinality constraints has been little investigated. The present work tackles a new problem of this class: the k-cardinality minimum cut problem (k-card cut). For a number of variants of this problem we show complexity results in the most signiΓΏcant graph classes. Moreover, we develop several heuristic algorithms for the k-card cut problem for complete, complete bipartite, and general graphs. Lower bounds are obtained through an SDP formulation, and used to show the quality of the heuristics. Finally, we present a randomized SDP heuristic and numerical results.

πŸ“œ SIMILAR VOLUMES

A branch-and-cut algorithm for the resou
A branch-and-cut algorithm for the resource-constrained minimum-weight arborescence problem
✍ Fischetti, Matteo; Vigo, Daniele πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 150 KB πŸ‘ 2 views

In this paper, we present a branch-and-cut algorithm for the exact solution of an NP-hard extension of the well-known Minimum-Weight Arborescence (MWA) problem, in which resource constraints for each node are considered. This Resource-Constrained Minimum-Weight Arborescence (RMWA) problem arises, e.

Minimum-cost strong network orientation
Minimum-cost strong network orientation problems: Classification, complexity, and algorithms
✍ Burkard, Rainer E.; Feldbacher, Karin; Klinz, Bettina; Woeginger, Gerhard J. πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 184 KB

In the minimum-cost strong network orientation problem (MCSO), we are given an undirected graph G Γ… (V, E) with nonnegative edge lengths ᐉ(e) and a transportation schedule T Γ… {(s 1 , t 1 , w 1 ), . . . , (s k , t k , w k )}, where w i units of weight have to be transported from the source vertex s