Mixed-integer vertex covers on bipartite graphs

M. Conforti, B. Gerards, G. Zambelli

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)
86 Downloads (Pure)

Abstract

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, xi 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.
Original languageEnglish
Title of host publicationProceedings of the 12th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2007) 25-27 June 2007, Ithaca ,New York, USA
EditorsM. Fischetti, D.P. Williamson
Place of PublicationBerlin, Germany
PublisherSpringer
Pages324-336
ISBN (Print)978-3-540-72791-0
DOIs
Publication statusPublished - 2007
Event12th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2007) - Ithaca, United States
Duration: 25 Jun 200727 Jun 2007
Conference number: 132

Publication series

NameLecture Notes in Computer Science
Volume4513
ISSN (Print)0302-9743

Conference

Conference12th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2007)
Abbreviated titleIPCO 2007
CountryUnited States
CityIthaca
Period25/06/0727/06/07

Fingerprint Dive into the research topics of 'Mixed-integer vertex covers on bipartite graphs'. Together they form a unique fingerprint.

Cite this