For every fixed k and g, maximum-weight stable sets can be found in polynomial time in graphs with odd cycle packing number at most k and Euler genus at most g.
The Integrality Number of an Integer Program
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We introduce the integrality number of an integer program (IP) in inequality form. Roughly speaking, the integrality number is the smallest number of integer constraints needed to solve an IP via a mixed integer (MIP) relaxation. One notable property of this number is its invariance under unimodular transformations of the constraint matrix. Considering the largest minor $\Delta$ of the constraint matrix, our analysis allows us to make statements of the following form: there exist numbers $\tau(\Delta)$ and $\kappa(\Delta)$ such that an IP with $n\geq \tau(\Delta)$ many variables and $n + \kappa(\Delta)\cdot \sqrt{n}$ many inequality constraints can be solved via a MIP relaxation with fewer than $n$ integer constraints. From our results it follows that IPs defined by only $n$ constraints can be solved via a MIP relaxation with $O(\sqrt{\Delta})$ many integer constraints.
fields
cs.DM 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
The stable set problem in graphs with bounded genus and bounded odd cycle packing number
For every fixed k and g, maximum-weight stable sets can be found in polynomial time in graphs with odd cycle packing number at most k and Euler genus at most g.