Faster width-dependent algorithm for mixed packing and covering LPs

Dec 11, 2019

Speakers

About

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/ε), 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√nw/\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 ε 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 ε. 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+ε approximation algorithm for the densest subgraph problem which runs in time O(md/ε), where m is the number of edges in the graph and d is the maximum graph degree.

Organizer

Categories

About NIPS 2019

Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.

Like the format? Trust SlidesLive to capture your next event!

Professional recording and live streaming, delivered globally.

Sharing

Recommended Videos

Presentations on similar topic, category or speaker

Interested in talks like this? Follow NIPS 2019