|
 
|
[WP16a] The Maximum Matrix Contraction problem : Appendix
Rapport Scientifique : Date de dépot: 2016/06/02, Nb pages 12, (Tech. Rep.: CEDRIC-16-3645)Mots clés: Complexity, Approximation algorithm, Linear Programming
Résumé:
This document contains the appendix of a paper accepted at the conference ISCO 2016, entitled The Maximum Matrix Contraction problem, this appendix could not be added to the camera-ready version due to lack of space. In the paper, we introduce the {\it 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 2 * sqrt(n)-approximation algorithm where $n$ is the number of ones in the matrix. We focused on three heuristics to solve the problem. In this appendix, we prove that, in the worst case, each algorithm returns an solution such that the ratio between an optimal density and the density of the returned solution is O(sqrt(n)).
Commentaires:
This document contains the appendix of a paper accepted at the conference ISCO 2016, this appendix could not be added to the camera-ready version due to lack of space. This document is presently incomplete, some explanations are missing, but it should be completed soon.
BibTeX
| @techreport { | |||
| WP16a, | |||
| title | = | "{The Maximum Matrix Contraction problem : Appendix}", | |
| author | = | "D. Watel and P. Poirion", | |
| number | = | "{CEDRIC-16-3645}", | |
| institution | = | "{CEDRIC laboratory, CNAM-Paris, France}", | |
| date | = | {02-06-2016}, | |
| pages | = | "12", | |
| note | = | "{This document contains the appendix of a paper accepted at the conference ISCO 2016, this appendix could not be added to the camera-ready version due to lack of space. This document is presently incomplete, some explanations are missing, but it should be completed soon.}", | |
| } | |||
