Campus Event Calendar
Event Entry
New for: D2, D3
What and Who
Biclique Completion Problem: Models and Algorithms
Claudio Magni
Politecnico di Milano
PhD Application Talk
Master student
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI
Public Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 21 February 2011
11:00
120 Minutes
E1 4
R024
Saarbrücken
Abstract
We consider the k-Clustering Minimum Biclique Completion Problem (k-MinBCP), which has been shown strongly 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.
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
IMPRS-CS Office
0681 93 25 225
--email hidden
passcode not visible
logged in users only
Heike Przybyl, 02/17/2011 15:34
Heike Przybyl, 02/17/2011 15:27 -- Created document.
Heike Przybyl, 02/17/2011 15:27 -- Created document.