<p>Consider a graph optimization on a graph with n vertices and m edges that can be written as an LP (like say bipartite matching). By the duality with vertex cover, we know that there's a sparse dual solution consisting of the  elements of the cover. It's sparse in the sense that its size is linear in n, rather than in m. </p>

<p>Consider the problem of finding the minimum enclosing ball of a set of $n$ points in $d$ dimensions. This is an LP-type problem with (again) a sparse dual solution: a set of $d+1$ points that define the optimal ball. Here, "sparse" means that the size depends on the (smaller) parameter $d$ rather than $n$</p>

<p>In general, suppose I have a problem that can be expressed via an LP with $n$ variables and $m$ constraints, where $m \gg n$. Are there classes of such  problems for which any optimal solution to the problem can be expressed using the intersection of only $O(n)$ constraints (or dually with only $O(n)$ nonzero dual variables ? </p>

CC BY-SA 3.0
2015-09-05T18:45:19.743Z
Surely with n variables the polytope is in $R^n$ and any basic feasible solution can be expressed as the intersection of $n$ of the linear constraints, by basic linear algebra. (?)
Neal Young
CC BY-SA 3.0
2015-09-11T05:51:41.643Z
But that's not the issue. For example in the MEB case there are n variables (indicators for which points to pick to define the ball), but you only need d+1 of them. In the matching case the primal LP has a variable for each edge (m of them), but you get a sparse dual solution that only involves n vertices.
Suresh Venkat
CC BY-SA 3.0
2015-09-12T15:43:07.090Z
True.  But my comment was about the problem you expressed in your third paragraph, about LP with n variables and m constraints.  Maybe instead of $O(n)$ you meant $o(n)$?
Neal Young
<ds.algorithms><linear-programming>
LPs with "sparse solutions"
Suresh Venkat
# LPs with "sparse solutions"

(Asked by: username_0 on 2015-09-05)

Consider a graph optimization on a graph with n vertices and m edges that can be written as an LP (like say bipartite matching). By the duality with vertex cover, we know that there's a sparse dual solution consisting of the elements of the cover. It's sparse in the sense that its size is linear in n, rather than in m.

Consider the problem of finding the minimum enclosing ball of a set of $n$ points in $d$ dimensions. This is an LP-type problem with (again) a sparse dual solution: a set of $d+1$ points that define the optimal ball. Here, "sparse" means that the size depends on the (smaller) parameter $d$ rather than $n$

In general, suppose I have a problem that can be expressed via an LP with $n$ variables and $m$ constraints, where $m \gg n$. Are there classes of such problems for which any optimal solution to the problem can be expressed using the intersection of only $O(n)$ constraints (or dually with only $O(n)$ nonzero dual variables ?

**Tags:** ds.algorithms, linear-programming
> **Comments:**
> **username_1**: Surely with n variables the polytope is in $R^n$ and any basic feasible solution can be expressed as the intersection of $n$ of the linear constraints, by basic linear algebra. (?)  
> **username_0**: But that's not the issue. For example in the MEB case there are n variables (indicators for which points to pick to define the ball), but you only need d+1 of them. In the matching case the primal LP has a variable for each edge (m of them), but you get a sparse dual solution that only involves n vertices.  
> **username_1**: True.  But my comment was about the problem you expressed in your third paragraph, about LP with n variables and m constraints.  Maybe instead of $O(n)$ you meant $o(n)$?  

---

## 0 answers

