The 2D Subarray Polytope | Zendy

Ivo Koch | Zendy; Javier Marenco | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

The 2D Subarray Polytope

Author(s) -

Ivo Koch,

Javier Marenco

Publication year - 2019

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2019.08.049

Subject(s) - polytope , column generation , integer programming , facet (psychology) , mathematical optimization , computer science , polytope model , linear programming , integer (computer science) , mathematics , branch and cut , scale (ratio) , algorithm , combinatorics , psychology , social psychology , physics , personality , quantum mechanics , big five personality traits , programming language

Given a d-dimensional array, the maximum subarray problem consists in finding an axis-parallel slice of the array maximizing the sum of its entries. In this work we start a polyhedral study of a natural integer programming formulation for this problem when d = 2. Such an exploration is motivated by the need of solving large-scale instances of the rectilinear picture compression problem (RPC), a problem which arises in different scenarios. The obtained results can be useful to solve the column generation phase of a branch and price approach for RPC, a technique that applies naturally to 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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research