Fast Approximation Algorithms for Fractional Packing and Covering Problems 3: An ε-Relaxed Decision Procedure for the General Problem Ax ≤ b, x ∈ P Using O(ρ²ε⁻² log(mρ/ε)) Oracle CallsResearch Paper
Many linear programs that arise in combinatorial optimization have a few "complicating" constraints on top of a set over which linear optimization is easy: multicommodity flow, where is a product of single-commodity flow polytopes; scheduling and the Held–Karp bound, where is a polytope of assignments or trees. Plotkin, Shmoys and Tardos…