Faster Primal-Dual Convergence for Min-Max Resource Sharing and Stronger Bounds via Local Weak Duality
We revisit the (block-angular) min-max resource sharing problem, which is a well-known generalization of fractional packing and the maximum concurrent flow problem. It consists of finding an ℓ_∞-minimal element in a Minkowski sum 𝒳= ∑_C ∈𝒞 X_C of non-empty closed convex sets X_C ⊆ℝ^ℛ_≥ 0, where 𝒞 and ℛ are finite sets. We assume that an oracle for approximate linear minimization over X_C is given. In this setting, the currently fastest known FPTAS is due to Müller, Radke, and Vygen. For δ∈ (0,1], it computes a σ(1+δ)-approximately optimal solution using 𝒪((|𝒞|+|ℛ|)log |ℛ| (δ^-2 + loglog |ℛ|)) oracle calls, where σ is the approximation ratio of the oracle. We describe an extension of their algorithm and improve on previous results in various ways. Our FPTAS, which, as previous approaches, is based on the multiplicative weight update method, computes close to optimal primal and dual solutions using 𝒪(|𝒞|+ |ℛ|/δ^2log |ℛ|) oracle calls. We prove that our running time is optimal under certain assumptions, implying that no warm-start analysis of the algorithm is possible. A major novelty of our analysis is the concept of local weak duality, which illustrates that the algorithm optimizes (close to) independent parts of the instance separately. Interestingly, this implies that the computed solution is not only approximately ℓ_∞-minimal, but among such solutions, also its second-highest entry is approximately minimal. We prove that this statement cannot be extended to the third-highest entry.
READ FULL TEXT