{"445161":{"#nid":"445161","#data":{"type":"event","title":"ARC\/ACO Colloquium: Alan Frieze - Carnegie Mellon University","body":[{"value":"\u003Cp\u003EPlease note the talk is at \u003Cstrong\u003E11 am\u003C\/strong\u003E in \u003Cstrong\u003E1116 East\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/p\u003E\u003Ch2 align=\u0022center\u0022\u003EAlan Frieze \u2013 Carnegie Mellon University\u003C\/h2\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EWednesday, September 23, 2015\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 E - 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003E(Refreshments will be served in Klaus 2222 at Noon)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003Cstrong\u003ETitle: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003ETitle: Probabilistic analysis of some combinatorial optimization problems.\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EWe consider the following probabilistic model. The edges of a (complete) graph have unknown random edge weights. We want to build a minimum cost structure. We can ask for the weight of an edge and then accept or reject the edge. Once rejected, the edge cannot be accepted later. We must accept enough edges to support a structure and we are charged for all the edges accepted, even if not used. We give results in this model for minimum spanning tree, perfect matching and shortest path.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;Joint work with Colin Cooper and Wesley Pegden.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Klaus 1116 East at 11 am  (Note: different day, time and location)"}],"uid":"27466","created_gmt":"2015-09-04 17:37:44","changed_gmt":"2017-04-13 21:18:22","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-09-23T12:00:00-04:00","event_time_end":"2015-09-23T13:00:00-04:00","event_time_end_last":"2015-09-23T13:00:00-04:00","gmt_time_start":"2015-09-23 16:00:00","gmt_time_end":"2015-09-23 17:00:00","gmt_time_end_last":"2015-09-23 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"related_links":[{"url":"http:\/\/www.math.cmu.edu\/~af1p\/","title":"Alan Frieze"},{"url":"http:\/\/www.arc.gatech.edu\/","title":"Algorithms \u0026 Randomness Center (ARC)"}],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"},{"id":"115001","name":"Computational Complexity"},{"id":"114991","name":"Computational Learning Theory"},{"id":"109","name":"Georgia Tech"},{"id":"140651","name":"Probabilistic Combinatorics"},{"id":"140661","name":"Theoretical Computer Science and Operations Research"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EDani Denton\u003Cbr \/\u003Edenton at cc dot gatech dot edu\u003Cbr \/\u003E\u003Cbr \/\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}