Adaptation of the Rounding Search-Based Algorithm for the k-Clustering Minimum Completion Problem - Université de Picardie Jules Verne Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

Adaptation of the Rounding Search-Based Algorithm for the k-Clustering Minimum Completion Problem

S. Sadeghsa
  • Fonction : Auteur
  • PersonId : 1227208
  • IdRef : 267668465

Résumé

This study proposes an algorithm based upon the rounding strategy for the k-clustering minimum completion problem. An instance of the problem is defined in a complete bipartite graph of S and C vertices. The goal of the problem is to decompose the initial graph into k-clusters, where each cluster is a complete bipartite subgraph. Since the problem is NP hard, any exact solver, like Cplex, is often not sufficient to achieve solutions with relatively hight quality. Thus, we propose a first alternative solution procedure for tackling large-scale instances. The designed method can be viewed as a special variant of the rounding search-based algorithm and it can be applied for solving several complex optimization problems. The proposed algorithm is evaluated on a set of benchmark instances related to the k-clustering minimum completion problem, where its achieved results are compared to the best results available in the literature.
Fichier non déposé

Dates et versions

hal-03617889 , version 1 (23-03-2022)

Identifiants

  • HAL Id : hal-03617889 , version 1

Citer

Mhand Hifi, S. Sadeghsa. Adaptation of the Rounding Search-Based Algorithm for the k-Clustering Minimum Completion Problem. 2020 7TH INTERNATIONAL CONFERENCE ON CONTROL, DECISION AND INFORMATION TECHNOLOGIES (CODIT'20), VOL 1, Jun 2020, Prague, Czech Republic. pp.1150-1155. ⟨hal-03617889⟩

Collections

U-PICARDIE EPROAD
11 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More