- Date
- Friday 14 Feb 2020, 12:00 - 13:00
- Type
- Seminar
- Spoken Language
- English
- Room
- Polak 2-16
- Building
- Polak Building
- Location
- Campus Woudestein
We investigate the Maximum Induced Matching problem (MIM), which is the problem of finding an induced matching having the largest cardinality on an undirected graph.
The problem is known to be NP-hard for general graphs. We first propose a vertex-based integer programming formulation, which is more compact compared to edge-based formulations in the literature. We also introduce vertex- and edge-weighted versions of MIM. We formulate the weighted problem as a quadratic integer programming problem based on our vertex-based formulation. We then linearize our quadratic programming formulation, and propose a decomposition algorithm that exploits a special structure of the linearized formulation. Our computational experiments show that our decomposition approach significantly improves solvability of the problem, especially on dense graphs.
Registration
For registration please send and email to the Econometric Institute secretarial office at eb-secr@ese.eur.nl. Registration is required for availability of lunch.
Organiser
- More information
Contact: Secretarial office, eb-secr@ese.eur.nl