2007

# Mixed-integer vertex covers on bipartite graphs

## Publication

### Publication

*Presented at the International Conference on Integer Programming and Combinatorial Optimization, Cornell University, Ithaca, NY, USA*

Let $A$ be the edge-node incidence matrix of a bipartite graph $G = (U, V ; E)$, $I$ be a subset of the nodes of $G$, and $b$ be a vector such that $2b$ is integral. We consider the following mixed-integer set: $X(G, b, I) = {x : Ax ≥ b, x ≥ 0, x_i$ integer for all $i ∈ I}$. We characterize conv$(X(G, b, I))$ in its original space. That is, we describe a matrix $(C, d)$ such that conv$(X(G, b, I)) = {x : Cx ≥ d}$. This is accomplished by computing the projection onto the space of the $x$-variables of an extended formulation, given in [1], for $conv(X(G, b, I))$. We then give a polynomial-time algorithm for the separation problem for conv$(X(G, b, I))$, thus showing that the problem of optimizing a linear function over the set $X(G, b, I)$ is solvable in polynomial time.

Additional Metadata | |
---|---|

Mixed integer programming (msc 90C11) | |

Springer | |

M. Fischetti , D.P. Williamson | |

Lecture Notes in Computer Science | |

Algorithmic Optimization Discretization | |

International Conference on Integer Programming and Combinatorial Optimization | |

Organisation | Probability, Networks and Algorithms |

Gerards, A.M.H, Conforti, M, & Zambelli, G. (2007). Mixed-integer vertex covers on bipartite graphs. In M Fischetti & D.P Williamson (Eds.),
Lecture Notes in Computer Science. Springer. |