In several applications the solutions of combinatorial optimization problems (COP) are required to satisfy an additional cardinality constraint, that is to contain a fixed 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 minimumc ut problem (k-card cut). For a number of variants of this problem we show complexity results in the most significant 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.
Cardinality constrained minimum cut problems: complexity and algorithms
BRUGLIERI, MAURIZIO;MAFFIOLI, FRANCESCO;
2004-01-01
Abstract
In several applications the solutions of combinatorial optimization problems (COP) are required to satisfy an additional cardinality constraint, that is to contain a fixed 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 minimumc ut problem (k-card cut). For a number of variants of this problem we show complexity results in the most significant 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.File | Dimensione | Formato | |
---|---|---|---|
Indice_DAM2004.pdf
Accesso riservato
:
Altro materiale allegato
Dimensione
85.71 kB
Formato
Adobe PDF
|
85.71 kB | Adobe PDF | Visualizza/Apri |
EditorialBoard_DAM2004.pdf
Accesso riservato
:
Altro materiale allegato
Dimensione
87.75 kB
Formato
Adobe PDF
|
87.75 kB | Adobe PDF | Visualizza/Apri |
Bruglieri_CardMinCut_DAM2004.pdf
Accesso riservato
:
Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione
376.74 kB
Formato
Adobe PDF
|
376.74 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.