On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms

We start with definitions given by Plotkin, Shmoys, and Tardos [16]. Given A∈ℝm×n, b∈ℝm and a polytope P $\subseteq$ ℝ n , the fractional packing problem is to find an x ∈ P such that Ax ≤ b if such an x exists. An ∈-approximate solution to this problem is an x ∈ P such that Ax ≤ (1+∈)b. An ∈-relaxed decision procedure always finds an ∈-approximate solution if an exact solution exists.