Faster p-norm minimizing flows, via smoothed q-norm problems
We present faster high-accuracy algorithms for computing $\ell_p$-norm minimizing flows. On a graph with $m$ edges, our algorithm can compute a $(1+1/\text{poly}(m))$-approximate unweighted $\ell_p$-norm minimizing flow with $pm^{1+\frac{1}{p-1}+o(1)}$ operations, for any $p \ge 2,$ giving the best...
Αποθηκεύτηκε σε:
| Κύριοι συγγραφείς: | , |
|---|---|
| Μορφή: | Άρθρο |
| Έκδοση: |
2019
|
| Θέματα: | |
| Διαθέσιμο Online: | https://arxiv.org/abs/1910.10571 http://arxiv.org/abs/1910.10571 |
| Ετικέτες: |
Δεν υπάρχουν, Καταχωρήστε ετικέτα πρώτοι!
|