Cyclic Transversal PolytopesOberseminar Discrete Optimization

by Volker Kaibel (Otto-von-Guericke-Universität Magdeburg)

Monday Feb 3, 2025, 6:15 PM → 7:15 PM Europe/Berlin

Arithmeum, Lennéstr., 2 - Seminarraum (Arithmeum / Research Institute for Discrete Mathematics)

We introduce the class of cyclic transversal polytopes (CTP’s) and the class of lifted odd set (LOS) inequalities for CTP’s. It turns out that several well-known polytopes that are relevant in Combinatorial Optimization are special cases of CTP’s, among them matching polytopes, stable set polytopes, and cut polytopes. We then show that the LOS inequalities are a common generalization of Edmonds’ inequalities for matching polytopes, the odd hole inequalities for stable set polytopes, and the cycle inequalities for cut polytopes. We furthermore discuss possibilities for generating relaxation hierarchies via CTP’s, where the first level is the relaxation obtained from the LOS inequalities. 

The talk is based on joint work with Jonas Frede, Maximilian Merkert, and Jannik Trappe.

 

The Oberseminar takes place in the Seminarraum, 1^st floor. Participants are invited to have coffee or tea in the lounge before.