[WP16] The Maximum Matrix Contraction problem

Conférence Internationale avec comité de lecture : 4th International Symposium on Combinatorial Optimization, May 2016, pp.1-12, France,

Mots clés: Complexity, Approximation algorithm, Linear Programming

Résumé: In this paper, we introduce the Maximum Matrix Contraction problem, where we aim to contract as much as possible a binary matrix in order to maximize its density. We study the complexity and the polynomial approximability of the problem. Especially, we prove this problem to be NP-Complete and that every algorithm solving this problem is at most an sqrt(n)-approximation algorithm where n is the number of ones in the matrix. We then focus on efficients algorithm to solve the problem: a linear program and three heuristics.

Commentaires: Accepté mais pas encore publié


@inproceedings {
title="{The Maximum Matrix Contraction problem}",
author=" D. Watel and P. Poirion ",
booktitle="{4th International Symposium on Combinatorial Optimization}",
address=" France",
note="{Accepté mais pas encore publié}",