I am working with a polytope $P\subset \mathbb{R}_+^n$ with the property that there are at about $n!$ minimizers of $\sum_{i=1}^n x_i$, in the following sense:
- Select any coordinate $j$ and set $x_j^* = \min\{x_j:x\in P\}$.
- Fix $x_j = x_j^*$ and pick any other coordinate $k$, and set $x_k^* = \min\{x_k : x\in P, x_j = x_j^*\}$.
- Fix $x_j = x_j^* , x_k = x_k^*$, pick any other coordinate $p$, and set $x_p^* = \min\{x_p : x\in P, x_j = x_j^*, x_k = x_k^*\}$
- Fix $x_j = x_j^* , x_k = x_k^*, x_p = x_p^*$, pick any other coordinate $q$, and set $x_q^* = \min\{x_q : x\in P, x_j = x_j^*, x_k = x_k^*, x_q = x_q^*\}$
(repeat this process $n-4$ more times by selecting a new coordinate each time and fixing all the predecessors)
It turns out that for my particular polytope $P$, the above procedure is guaranteed to find a solution within $1\%$ of optimality for the objective of minimizing $\sum_{i=1}^n x_i$, for any sequence of coordinates that we minimize (and of course there are $n!$ such sequences).
My question is: does this tell me anything useful about the general linear program of minimizing $\sum_{i=1}^n c_i x_i $ over $P$?
