Faster width-dependent algorithm for mixed packing and covering LPs

11. Prosinec 2019

Řečníci

O prezentaci

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.

Organizátor

Kategorie

O organizátorovi (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.

Uložení prezentace

Měla by být tato prezentace uložena po dobu 1000 let?

Jak ukládáme prezentace

Pro uložení prezentace do věčného trezoru hlasovalo 0 diváků, což je 0.0 %

Sdílení

Doporučená videa

Prezentace na podobné téma, kategorii nebo přednášejícího

Zajímají Vás podobná videa? Sledujte NIPS 2019