{"42826":{"#nid":"42826","#data":{"type":"event","title":"Fast gradient methods for network flow problems","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETITLE:\u003C\/strong\u003E  Fast gradient methods for network flow problems\n\u003C\/p\u003E\n\u003Cp\u003E\u003Cstrong\u003ESPEAKER:\u003C\/strong\u003E  Dr. Yuri Nesterov\n\u003C\/p\u003E\n\u003Cp\u003E\u003Cstrong\u003EABSTRACT:\u003C\/strong\u003E\n\u003C\/p\u003E\n\u003Cp\u003EIn this talk we present a new approach for finding approximate solutions to different network problems related to multi-commodity flows. We consider simple subgradient schemes and schemes based on the smoothing technique. The fastest of our methods solves the maximal concurrent flow problem in $O({qm ln n over delta})$ iterations, where $delta$ is the related accuracy, $m$ and $n$ are the number of arcs\/nodes in the graph, and $q$ is the number\u003Cbr \/\u003E\nof commodity sources. Each iteration of these schemes is very simple and does not require any sophisticated operations (e.g. shortest path computation). Its complexity is of the order $O(mq ln q)$ operations. The application of our approach needs a preliminary computational stage\u003Cbr \/\u003E\nconsisting in finding all node-to-node maximal flows, which takes $O(n2 m ln n)$ operations. \u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"Fast gradient methods for network flow problems","format":"limited_html"}],"field_summary_sentence":[{"value":"Fast gradient methods for network flow problems"}],"uid":"27187","created_gmt":"2009-10-12 20:36:11","changed_gmt":"2016-10-08 01:47:09","author":"Anita Race","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2009-04-07T12:00:00-04:00","event_time_end":"2009-04-07T13:00:00-04:00","event_time_end_last":"2009-04-07T13:00:00-04:00","gmt_time_start":"2009-04-07 16:00:00","gmt_time_end":"2009-04-07 17:00:00","gmt_time_end_last":"2009-04-07 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"1242","name":"School of Industrial and Systems Engineering (ISYE)"}],"categories":[],"keywords":[{"id":"5312","name":"gradient"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cstrong\u003EAnita  Race\u003C\/strong\u003E\u003Cbr \/\u003EH. Milton Stewart School of Industrial and Systems Engineering\u003Cbr \/\u003E\u003Ca href=\u0022http:\/\/www.gatech.edu\/contact\/index.html?id=ar9\u0022\u003EContact Anita  Race\u003C\/a\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}