[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,

Auteurs: D. Watel , P. Poirion

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.

Download

BibTeX

@inproceedings {
	WP16,
	title	=	"{The Maximum Matrix Contraction problem}",
	author	=	" D. Watel and P. Poirion ",
	booktitle	=	"{4th International Symposium on Combinatorial Optimization}",
	year	=	2016,
	month	=	"May",
	pages	=	"1-12",
	address	=	" France",
	note	=	"{AcceptÃ© mais pas encore publiÃ©}",
}