Strengthened clique-family inequalities for the stable set polytope |
| |
| Affiliation: | 1. Department of Management Science, Lancaster University, Lancaster LA1 4YX, UK;2. Istituto di Analisi dei Sistemi ed Informatica (IASI) del CNR, Via dei Taurini 19, Roma 00185, Italy |
| |
| 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. |
| |
| Keywords: | Combinatorial optimization Stable set problem Polyhedral combinatorics |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
