New answers tagged linear-programming
2
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{...
Top 50 recent answers are included
