Poster
Faster width-dependent algorithm for mixed packing and covering LPs
Digvijay Boob · Saurabh Sawlani · Di Wang
East Exhibition Hall B, C #232
Keywords: [ Combinatorial Optimization ] [ Optimization ] [ Density Estimation ] [ Algorithms ]
[
Abstract
]
Abstract:
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 approximate solution in time , where is number of nonzero entries in the constraint matrix, and is the maximum number of nonzeros in any constraint. This algorithm is faster than Nesterov's smoothing algorithm which requires time, where 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 while breaking the infamous barrier to eliminate the factor of . The current best width-independent algorithm for this problem runs in time [Young-arXiv-14] and hence has worse running time dependence on . 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 approximation algorithm for the densest subgraph problem which runs in time , where is the number of edges in the graph and is the maximum graph degree.
Live content is unavailable. Log in and register to view live content