# LP-type vs. Approximation

I'm interested in an computational geometry problem that's sensibly expressed as an infinite dimensional 0-1 integer program. I'm not worried about finding an actual minimum for the objective function, any solution with isn't stupidly big will do. It thus seems natural to apply an approximation algorithm that starts by running simplex or similar restricted to $[0,1]$.

I'd expect the solutions usually require only a few hundred dimensions, but any naive restriction of the problem space yields millions of dimensions. As I understand it, good implementations of a linear program solver should be polynomial time in both the dimension and constraints on average cases, but nevertheless this problem chokes GLPK. Should GLPK really choke on a million dimensions?

I've therefore started looking for less naive restrictions of the problem space, which lead me to LP-type problems. In particular, there is a claim that Clarkson's algorithm applied to linear programs are equivalent to running the simplex algorithm on the dual problem. In what sense is this true?

I find this claim highly dubious with respect to complexity for several reasons. First, Clarkson's algorithm does not exploit any $[0,1]$ solutions with fast average case solutions, but merely randomly chooses pivots. Second, Clarkson's algorithm has running time worse than exponential in the dimension $O(dn + d! d^k \log n)$, which doesn't rule out polynomial time for average cases, but I haven't found that fact yet.

As an aside, any nice examples of improving a restriction of an infinite dimensional linear program over time?

• I take it your LP has infinitely many variables. How many constraints does it have? If you have finitely many constraints, you might consider Lagrangian-relaxation algorithms (or column generation). – Neal Young Dec 2 '12 at 21:28
• Clarkson's algorithm combined with the Matousek-Sharir-Welzl technique yields a sub-exponential time algorithm for linear program. I believe the bound is something like $\exp(\sqrt{d})$. – Suresh Venkat Dec 2 '12 at 21:30
• I'll look up Matousek-Sharir-Welzl then, thanks. I'm unclear if that's any faster than traditional 0-1 methods based upon simplex or whatever though, but thanks. – Jeff Burdges Dec 3 '12 at 1:15
• Yes, I have only finitely many constraints. Yes, column generation looks very relevant, but I'll need to read about it. Is your point that the Lagrangian dual problem has only finitely many variables? I'm unsure how one gets enough information about the Lagrangian dual problem, but maybe that's what you meant by column generation or something. Thanks! – Jeff Burdges Dec 3 '12 at 2:08
• If the problem can be formulated as, say, a fractional covering LP with finitely many constraints, then you can approximately solve it with an iterative Lagrangian-relaxation algorithm as long as, in each iteration, from a given linear combination $v\cdot A$ of the constraints, you can compute a variable such that $v\cdot A^T_j \ge 1$ (given that such a variable exists). See this discussion and Y01. – Neal Young Dec 3 '12 at 16:04