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.
Cut problems, k-cardinality minimum cut, Cardinality constrained combinatorial optimization
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/555764
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 15
social impact