2024/07/02 by Khaled Elbassioni, Elbassioni, Khaled
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Matrix Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2407.02201
openalex publication_date 2024/07/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the monotone integer dualization problem, we are given two sets of vectors in an integer box such that no vector in the first set is dominated by a vector in the second. The question is to check if the two sets of vectors cover the entire integer box by upward and downward domination, respectively. It is known that the problem is (quasi-)polynomially equivalent to that of enumerating all maximal feasible solutions of a given monotone system of linear/separable/supermodular inequalities over integer vectors. The equivalence is established via showing that the dual family of minimal infeasible vectors has size bounded by a (quasi-)polynomial in the sizes of the family to be generated and the input description. Continuing in this line of work, in this paper, we consider systems of polynomial, second-order cone, and semidefinite inequalities. We give sufficient conditions under which such bounds can be established and highlight some applications.