# Tag Info

The LP in question is a maximization over a bounded polytope, hence the optimal value is attained at a vertex of the polytope. Moreover, any vertex can be described as a unique solution of a system of linear equations obtained by replacing inequalities with equalities in a subset of the inequalities defining the problem. Here, the polytope is defined by $$\... 0 This is discussed in a related cstheory post: LP relaxation of independent set That post cites this publication: [1] Nemhauser, G.L., Trotter, L.E. Vertex packings: Structural properties and algorithms. Mathematical Programming 8, 232–248 (1975). https://doi.org/10.1007/BF01580444 That publication in turn cites a few others, including these: [2] ... 2 Depending on how people interpret "research-level", this might need to be moved to cs.stackexchange.com. The intuition becomes more apparent if you first write down an alternate similar looking but not necessarily linear mathematical program$$\begin{eqnarray} \textrm{maximize}\,\,&\tfrac{\sum_{(i,j) \in E} x_{ij}}{\sum_{i \in V} y_i}& \\ \textrm{...