The stable set polytope is a fundamental object in combinatorial optimization. Among the many valid inequalities that are known for it, the clique-family inequalities play an important role. Pêcher and Wagler showed that the clique-family inequalities can be strengthened under certain conditions. We show that they can be strengthened even further, using a surprisingly simple mixed-integer rounding argument.
Strengthened clique-family inequalities for the stable set polytope
Ventura P
2021
Abstract
The stable set polytope is a fundamental object in combinatorial optimization. Among the many valid inequalities that are known for it, the clique-family inequalities play an important role. Pêcher and Wagler showed that the clique-family inequalities can be strengthened under certain conditions. We show that they can be strengthened even further, using a surprisingly simple mixed-integer rounding argument.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
