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 ?

  • $\begingroup$ 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. (?) $\endgroup$ – Neal Young Sep 5 '15 at 18:45
  • $\begingroup$ 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. $\endgroup$ – Suresh Venkat Sep 11 '15 at 5:51
  • $\begingroup$ 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)$? $\endgroup$ – Neal Young Sep 12 '15 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.