| dc.creator | Marenco, Javier | |
| dc.creator | Koch, Ivo | |
| dc.date.accessioned | 2023-06-15T14:19:10Z | |
| dc.date.accessioned | 2024-08-01T16:54:44Z | |
| dc.date.available | 2023-06-15T14:19:10Z | |
| dc.date.available | 2024-08-01T16:54:44Z | |
| dc.date.created | 2023-06-15T14:19:10Z | |
| dc.date.issued | 2022 | |
| dc.identifier | https://repositorio.utdt.edu/handle/20.500.13098/11877 | |
| dc.identifier | https://doi.org/10.1016/j.dam.2021.09.031 | |
| dc.identifier.uri | https://repositorioslatinoamericanos.uchile.cl/handle/2250/9536967 | |
| 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. | |
| dc.relation | 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 | https://creativecommons.org/licenses/by-sa/2.5/ar/ | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.subject | Maximum subarray problem | |
| dc.subject | Integer programming | |
| dc.subject | Facets | |
| dc.title | The maximum 2D subarray polytope: facet-inducing inequalities and polyhedral computations | |
| dc.type | info:eu-repo/semantics/preprint | |
