Campus Event Calendar
Event Entry
New for: D3
What and Who
k-Clustering Minimum Biclique Completion
Claudio Magni
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 22 June 2011
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We consider the k-Clustering Minimum Biclique Completion Problem (k-MinBCP), which has been shown to be NP-hard. Given a bipartite graph G = (S,T,E), the objective is to find k bipartite subgraphs, called "clusters", while minimizing the total number of edges needed to make each cluster complete (i.e. to become a biclique), such that each vertex i of S appears in exactly one cluster and every vertex j of T appears in each cluster in which at least one of its neighbors appears.
It has applications in telecommunications and, in particular, in bundling channels for multicast transmissions.
We analyze several Integer Programming formulations and implement a Branch-and-Price algorithm, which features a non-trivial branching rule and takes advantage of a new metaheuristic based on Variable Neighborhood Unfeasible Search (VNUS). Computational results show that this approach outperforms other state of the art methods found in the literature, allowing to exactly solve larger instances of k-MinBCP.
Contact
Claudio Magni
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Multicast Partition, Biclique, Branch-and-Price, Local Search
Claudio Magni, 06/10/2011 17:28 -- Created document.