Show simple item record

dc.contributor.author
Kyng, Rasmus
dc.contributor.author
Peng, Richard
dc.contributor.author
Sachdeva, Sushant
dc.contributor.author
Wang, Di
dc.date.accessioned
2020-02-03T13:16:16Z
dc.date.available
2020-01-14T14:42:43Z
dc.date.available
2020-02-03T13:16:16Z
dc.date.issued
2019-06
dc.identifier.isbn
978-1-4503-6705-9
en_US
dc.identifier.other
10.1145/3313276.3316410
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/390425
dc.description.abstract
We present algorithms for solving a large class of flow and regression problems on unit weighted graphs to (1 + 1 / poly(n)) accuracy in almost-linear time. These problems include ℓp-norm minimizing flow for p large (p ∈ [ω(1), o(log2/3n) ]), and their duals, ℓp-norm semi-supervised learning for p close to 1. As p tends to infinity, p-norm flow and its dual tend to max-flow and min-cut respectively. Using this connection and our algorithms, we give an alternate approach for approximating undirected max-flow, and the first almost-linear time approximations of discretizations of total variation minimization objectives. Our framework is inspired by the routing-based solver for Laplacian linear systems by Spielman and Teng (STOC ’04, SIMAX ’14), and is based on several new tools we develop, including adaptive non-linear preconditioning, tree-routings, and (ultra-)sparsification for mixed ℓ2 and ℓp norm objectives.
en_US
dc.language.iso
en
en_US
dc.publisher
ACM Press
en_US
dc.subject
Network flows
en_US
dc.subject
convex optimization
en_US
dc.subject
graph sparsification
en_US
dc.subject
precon-ditioning
en_US
dc.title
Flows in almost linear time via adaptive preconditioning
en_US
dc.type
Conference Paper
ethz.book.title
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019
en_US
ethz.pages.start
902
en_US
ethz.pages.end
913
en_US
ethz.event
51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019)
en_US
ethz.event.location
Phoenix, AZ, USA
en_US
ethz.publication.place
New York, NY
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::09687 - Kyng, Rasmus / Kyng, Rasmus
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::09687 - Kyng, Rasmus / Kyng, Rasmus
en_US
ethz.date.deposited
2020-01-14T14:42:51Z
ethz.source
FORM
ethz.eth
no
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2020-02-03T13:16:26Z
ethz.rosetta.lastUpdated
2020-02-03T13:16:26Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Flows%20in%20almost%20linear%20time%20via%20adaptive%20preconditioning&rft.date=2019-06&rft.spage=902&rft.epage=913&rft.au=Kyng,%20Rasmus&Peng,%20Richard&Sachdeva,%20Sushant&Wang,%20Di&rft.isbn=978-1-4503-6705-9&rft.genre=proceeding&rft_id=info:doi/10.1145/3313276.3316410&rft.btitle=Proceedings%20of%20the%2051st%20Annual%20ACM%20SIGACT%20Symposium%20on%20Theory%20of%20Computing,%20STOC%202019
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record