Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleCharacterizations of total dual integrality.
Author(s) Edwin OShea, Alexander A. Razborov
TypeBook, Chapter in Book, Conference Proceeding
AbstractIn this paper we provide new characterizing properties of TDI systems. A corollary is Sturmfels’ theorem relating toric initial ideals generated by square-free monomials to unimodular triangulations. A reformulation of these test-sets to polynomial ideals actually generalizes the existence of square-free monomials to arbitrary TDI systems, providing new relations between integer programming and Gröbner bases of toric ideals. We finally show that stable set polytopes of perfect graphs are characterized by a refined fan that is a triangulation consisting only of unimodular cones, a fact that endows the Weak Perfect Graph Theorem with a computationally advantageous geometric feature. Three ways of implementing the results are described and some experience about one of these is reported.
ISBN978-3-540-72791-0/pbk
URL http://link.springer.com/chapter/10.1007%2F978-3-540-72792-7_29
LanguageEnglish
Pages382--396
PublisherBerlin: Springer
Year2007
Edition0
Translation No
Refereed No
Webmaster