# Faster width-dependent algorithm for mixed packing and covering LPs

arXiv: https://arxiv.org/abs/1909.12387 · HTML: https://mlsanity.com/paper/1909.12387/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Sep 2019.

## Built on by (most cited first, 3 of 3)

- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (2023)
- [The Oracle Complexity of Simplex-based Matrix Games](https://mlsanity.com/paper/2412.06990/) (2024)
- [Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems](https://mlsanity.com/paper/2505.17443/) (2025)

## Abstract (arXiv)

In this paper, we give a faster width-dependent algorithm for mixed packing-covering LPs. Mixed packing-covering LPs are fundamental to combinatorial optimization in computer science and operations research. Our algorithm finds a 1+eps approximate solution in time O(Nw/ eps), where N is number of nonzero entries in the constraint matrix and w is the maximum number of nonzeros in any constraint. This run-time is better than Nesterov's smoothing algorithm which requires O(N√nw/ eps) where n is the dimension of the problem. Our work utilizes the framework of area convexity introduced in [Sherman-FOCS'17] to obtain the best dependence on eps while breaking the infamous ℓ∞ barrier to eliminate the factor of √n. The current best width-independent algorithm for this problem runs in time O(N/eps2) [Young-arXiv-14] and hence has worse running time dependence on eps. Many real life instances of the mixed packing-covering problems exhibit small width and for such cases, our algorithm can report higher precision results when compared to width-independent algorithms. As a special case of our result, we report a 1+eps approximation algorithm for the densest subgraph problem which runs in time O(md/ eps), where m is the number of edges in the graph and d is the maximum graph degree.