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?