| dc.rights.license | https://creativecommons.org/licenses/by-sa/2.5/ar/ | es_AR |
| dc.contributor.author | Marenco, Javier | es_AR |
| dc.contributor.author | Koch, Ivo | es_AR |
| dc.date.accessioned | 2023-06-15T14:19:10Z | |
| dc.date.available | 2023-06-15T14:19:10Z | |
| dc.date.issued | 2022 | |
| dc.identifier.uri | https://repositorio.utdt.edu/handle/20.500.13098/11877 | |
| dc.identifier.uri | https://doi.org/10.1016/j.dam.2021.09.031 | |
| dc.description.abstract | Given a matrix with real-valued entries, the maximum 2D subarray problem
consists in finding a rectangular submatrix with consecutive rows and columns
maximizing the sum of its entries. In this work we start a polyhedral study
of an integer programming formulation for this problem.We thus define the 2D
subarray polytope, explore conditions ensuring the validity of linear inequalities,
and provide several families of facet-inducing inequalities. We also report com-
putational experiments assessing the reduction of the dual bound for the linear
relaxation achieved by these families of inequalities. | es_AR |
| dc.description.sponsorship | Este documento es una versión del artículo publicado en Applied Mathematics 323, 286-301. | es_AR |
| dc.format.extent | 34 p. | es_AR |
| dc.format.medium | application/pdf | es_AR |
| dc.language | eng | es_AR |
| dc.relation.isversionof | Koch, I., & Marenco, J. (2022). The maximum 2D subarray polytope: Facet-inducing inequalities and polyhedral computations. Discrete Applied Mathematics, 323, 286–301. https://doi.org/10.1016/j.dam.2021.09.031 | |
| dc.rights | info:eu-repo/semantics/openAccess | es_AR |
| dc.subject | Maximum subarray problem | es_AR |
| dc.subject | Integer programming | es_AR |
| dc.subject | Facets | es_AR |
| dc.title | The maximum 2D subarray polytope: facet-inducing inequalities and polyhedral computations | es_AR |
| dc.type | info:eu-repo/semantics/preprint | es_AR |
| dc.type.version | info:eu-repo/semantics/submittedVersion | es_AR |
