Oral
Faster width-dependent algorithm for mixed packing and covering LPs
Digvijay Boob · Saurabh Sawlani · Di Wang

Wed Dec 11th 10:05 -- 10:20 AM @ West Ballroom C

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/ \varepsilon)$, where $N$ is number of nonzero entries in the constraint matrix, and $w$ is the maximum number of nonzeros in any constraint. This algorithm is faster than Nesterov's smoothing algorithm which requires $O(N\sqrt{n}w/ \eps)$ time, 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 $\varepsilon$ while breaking the infamous $\ell_{\infty}$ barrier to eliminate the factor of $\sqrt{n}$. The current best width-independent algorithm for this problem runs in time $O(N/\eps^2)$ [Young-arXiv-14] and hence has worse running time dependence on $\varepsilon$. Many real life instances of 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+\varepsilon$ approximation algorithm for the densest subgraph problem which runs in time $O(md/ \varepsilon)$, where $m$ is the number of edges in the graph and $d$ is the maximum graph degree.

Author Information

Digvijay Boob (Georgia Institute of Technology)

I am **Digvijay**, fifth year PhD student in *Algorithms, Combinatorics and Optimization* at Georgia Institute of Technology with home unit in ISyE. My core area of research is development of algorithms for non-convex optimization and saddle point problems, focusing primarily on first-order algorithms with provable convergence rates.

Saurabh Sawlani (Georgia Institute of Technology)

* 5th year PhD student in the Algorithms, Combinatorics and Optimization program at Georgia Tech. * Primarily work on graph algorithms, and applications to data mining.

Di Wang (Google AI)

Related Events (a corresponding poster, oral, or spotlight)