{"52797":{"#nid":"52797","#data":{"type":"event","title":"ARC ThinkTank Colloquium-Navin Goyal","body":[{"value":"\u003Cp\u003EMarch 10, 2008\u003Cbr \/\u003ENavin Goyal\u003Cbr \/\u003EARC ThinkTank, Georgia Tech, College of Computing\u003C\/p\u003E\n\u003Cp\u003ETitle: Network design under traffic uncertainty\u003C\/p\u003E\n\u003Cp\u003EAbstract: We consider the following network design problem.\u00a0\u003C\/p\u003E\n\u003Cp\u003EA group of nodes (terminals) in a large network wishes to reserve bandwidth to form a sub-network called virtual private network (VPN).\u00a0The VPN should be able to support various communication patterns that may arise between the terminals.\u00a0These communication patterns may change with time, and the only restriction on them is that for each terminal there is an upper bound on the total amount of traffic handled by that terminal.\u00a0This leads to the well-studied VPN design problem wherein we must find paths between every pair of terminals and reserve sufficient capacity on the edges on these paths so that all possible communication patterns satisfying the given upper bounds can be routed. Each edge has cost proportional to the bandwidth reserved on it. The goal is to minimize the total cost of the VPN.\u003C\/p\u003E\n\u003Cp\u003EA well-known conjecture states that the optimal VPN is a tree.\u00a0In this talk, I will explain our recent proof of this conjecture.\u00a0This also yields\u003Cbr \/\u003Ethe first polynomial time algorithm for computing the optimal VPN.\u00a0\u003C\/p\u003E\n\u003Cp\u003EThis is joint work with Neil Olver and Bruce Shepherd.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27154","created_gmt":"2010-02-11 15:57:53","changed_gmt":"2016-10-08 01:50:09","author":"Louise Russo","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2008-03-10T16:00:00-04:00","event_time_end":"2008-03-10T17:00:00-04:00","event_time_end_last":"2008-03-10T17:00:00-04:00","gmt_time_start":"2008-03-10 20:00:00","gmt_time_end":"2008-03-10 21:00:00","gmt_time_end_last":"2008-03-10 21:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"allyana ziolko","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}