Electric routing and concurrent flow cutting
We investigate an oblivious routing scheme amenable to distributed computation and resilient to graph changes, based on electrical flow. Our main technical contribution is a new rounding method which we use to obtain a bound on the L[subscript 1]-->L[subscript 1] operator norm of the inverse grap...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2012
|
| Online Access: | http://hdl.handle.net/1721.1/71604 https://orcid.org/0000-0002-4257-4198 |
| _version_ | 1826204966033817600 |
|---|---|
| author | Adam, Jonathan Adam Maymounkov, Petar Borissov |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Adam, Jonathan Adam Maymounkov, Petar Borissov |
| author_sort | Adam, Jonathan Adam |
| collection | MIT |
| description | We investigate an oblivious routing scheme amenable to distributed computation and resilient to graph changes, based on electrical flow. Our main technical contribution is a new rounding method which we use to obtain a bound on the L[subscript 1]-->L[subscript 1] operator norm of the inverse graph Laplacian. |
| first_indexed | 2024-09-23T13:04:26Z |
| format | Article |
| id | mit-1721.1/71604 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:04:26Z |
| publishDate | 2012 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/716042022-10-01T12:54:10Z Electric routing and concurrent flow cutting Adam, Jonathan Adam Maymounkov, Petar Borissov Massachusetts Institute of Technology. Department of Mathematics Kelner, Jonathan Adam Kelner, Jonathan Adam Maymounkov, Petar Borissov We investigate an oblivious routing scheme amenable to distributed computation and resilient to graph changes, based on electrical flow. Our main technical contribution is a new rounding method which we use to obtain a bound on the L[subscript 1]-->L[subscript 1] operator norm of the inverse graph Laplacian. National Science Foundation (U.S.) (NSF grant CCF-0843915) 2012-07-12T19:19:55Z 2012-07-12T19:19:55Z 2009-12 2009-09 Article http://purl.org/eprint/type/ConferencePaper 9783642106309 0302-9743 http://hdl.handle.net/1721.1/71604 Kelner, Jonathan, and Petar Maymounkov. “Electric Routing and Concurrent Flow Cutting.” Algorithms and Computation. Ed. Yingfei Dong, Ding-Zhu Du, & Oscar Ibarra. (Lecture Notes in Computer Science ; Vol. 5878). Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. 792–801. Web. https://orcid.org/0000-0002-4257-4198 en_US http://dx.doi.org/10.1007/978-3-642-10631-6_80 Algorithms and Computation, Proceedings of the 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009 Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer-Verlag MIT web domain |
| spellingShingle | Adam, Jonathan Adam Maymounkov, Petar Borissov Electric routing and concurrent flow cutting |
| title | Electric routing and concurrent flow cutting |
| title_full | Electric routing and concurrent flow cutting |
| title_fullStr | Electric routing and concurrent flow cutting |
| title_full_unstemmed | Electric routing and concurrent flow cutting |
| title_short | Electric routing and concurrent flow cutting |
| title_sort | electric routing and concurrent flow cutting |
| url | http://hdl.handle.net/1721.1/71604 https://orcid.org/0000-0002-4257-4198 |
| work_keys_str_mv | AT adamjonathanadam electricroutingandconcurrentflowcutting AT maymounkovpetarborissov electricroutingandconcurrentflowcutting |