Linear Programming Complementation

10^th May 2022, 13:00 Ashton Lecture Theatre
Dr. Maximilien Gadouleau
Department of Computer Science, Durham University

Abstract

In this talk, we introduce a new kind of duality for Linear Programming (LP), that we call LP complementation. We prove that the optimal values of an LP and of its complement are complement pairs (provided that either the original LP or its complement has an optimal value greater than one). The main consequence of the LP complementation theorem is for hypergraphs. We introduce the complement of a hypergraph and we show that the fractional packing numbers of a hypergraph and of its complement are complement pairs; similar results hold for fractional matching, covering and transversal numbers.

This hypergraph complementation theorem has several consequences for fractional graph theory. In particular, we relate the fractional dominating number of a graph to the fractional total dominating number of its complement.