Total dual dyadicness and dyadic generating sets

• 成果类型: Article
• 署名作者: Abdi, Ahmad; Cornuejols, Gerard; Guenin, Bertrand; Tuncel, Levent
• 署名单位: University of London; London School Economics & Political Science; Carnegie Mellon University; University of Waterloo
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-01967-z
• 发表日期: 2024
• 页码: 125-143
• 关键词: graphs; integrality; systems; SMITH

摘要

A vector is dyadic if each of its entries is a dyadic rational number, i.e. of the form (a)/(2)k for some integers a, k with k = 0. A linear system Ax = b with integral data is totally dual dyadic if whenever min{b(T)y : A(T)y = w, y = 0J for w integral, has an optimal solution, it has a dyadic optimal solution. In this paper, we study total dual dyadicness, and give a co-NP characterization of it in terms of dyadic generating sets for cones and subspaces, the former being the dyadic analogue of Hilbert bases, and the latter a polynomial-time recognizable relaxation of the former. Along the way, we see some surprising turn of events when compared to total dual integrality, primarily led by the density of the dyadic rationals. Our study ultimately leads to a better understanding of total dual integrality and polyhedral integrality. We see examples from dyadic matroids, T-joins, cycles, and perfect matchings of a graph.