Back to Search
Start Over
Persistency of linear programming relaxations for the stable set problem
- Source :
- Mathematical programming. Springer
- Publication Year :
- 2021
- Publisher :
- Springer Science and Business Media LLC, 2021.
-
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 other LP formulations have been studied and one may wonder whether any of them has this property as well. We show that any other formulation that satisfies mild conditions cannot have the persistency property on all graphs, unless it is always equal to the stable set polytope.<br />Comment: 17 pages, 6 figures
- Subjects :
- FOS: Computer and information sciences
Property (philosophy)
Discrete Mathematics (cs.DM)
Linear programming
General Mathematics
0211 other engineering and technologies
Polytope
010103 numerical & computational mathematics
02 engineering and technology
01 natural sciences
Combinatorics
Integer
FOS: Mathematics
Mathematics - Combinatorics
0101 mathematics
Mathematics - Optimization and Control
Integer programming
Mathematics
021103 operations research
Numerical analysis
Optimization and Control (math.OC)
Independent set
Combinatorics (math.CO)
Variety (universal algebra)
Software
Computer Science - Discrete Mathematics
Subjects
Details
- ISSN :
- 14364646 and 00255610
- Volume :
- 192
- Database :
- OpenAIRE
- Journal :
- Mathematical Programming
- Accession number :
- edsair.doi.dedup.....c1da7341d3e2b6ecd1ff548e1b687ace