Abstract
The Nemhauser-Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: for every optimal LP solution that assigns integer values to some variables, there exists an optimal integer solution in which these variables retain the same values. While the standard LP is defined by only non-negativity and edge constraints, a variety of stronger LP formulations have been studied and one may wonder whether any of them has the this property as well. We show that any stronger LP formulation that satisfies mild conditions cannot have the persistency property on all graphs, unless it is always equal to the stable-set polytope.
Original language | English |
---|---|
Title of host publication | Integer Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, Proceedings |
Editors | Daniel Bienstock, Giacomo Zambelli |
Publisher | Springer |
Pages | 351-363 |
Number of pages | 13 |
ISBN (Electronic) | 978-3-030-45771-6 |
ISBN (Print) | 978-3-030-45770-9 |
DOIs | |
Publication status | Published - 14 Apr 2020 |
Event | 21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020 - London, United Kingdom Duration: 8 Jun 2020 → 10 Jun 2020 Conference number: 21 http://www.lse.ac.uk/IPCO-2020 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Volume | 12125 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020 |
---|---|
Abbreviated title | IPCO 2020 |
Country/Territory | United Kingdom |
City | London |
Period | 8/06/20 → 10/06/20 |
Other | Online conference |
Internet address |
Keywords
- Integer linear programming
- Persistency
- Stable set
- 22/2 OA procedure