{"349751":{"#nid":"349751","#data":{"type":"event","title":"ARC Colloquium: Seth Pettie\u2013University of Michigan","body":[{"value":"\u003Cp\u003E(Refreshments will be served in Klaus 2222 at 2 pm)\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E \u003Cbr \/\u003EWeighted Matching on General Graphs: Faster and Simpler\u003Cbr \/\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract :\u003C\/strong\u003E\u003Cbr \/\u003EWe present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs.\u0026nbsp; The algorithm runs in O(mn^{1\/2}log(nW)) time, where m, n, and W are the numbers of edges, vertices and maximum integer edge weight.\u0026nbsp; This bound matches the fastest algorithm for bipartite graphs and comes within a log(nW) factor of the Micali-Vazirani cardinality matching algorithm.\u0026nbsp;\u0026nbsp; In terms of running time our algorithm is just slightly faster than the previous best (Gabow and Tarjan, 1991) by a roughly (log n)^{1\/2} factor.\u0026nbsp; However, it is dramatically simpler to describe and analyze. \u003C\/p\u003E\u003Cp\u003EJoint work with Ran Duan (IIIS, Tsinghua) and Hsin-Hao Su (University of Michigan).\u0026nbsp; Manuscript available at \u003Ca href=\u0022http:\/\/arxiv.org\/abs\/1411.1919v2\u0022 title=\u0022http:\/\/arxiv.org\/abs\/1411.1919v2\u0022\u003Ehttp:\/\/arxiv.org\/abs\/1411.1919v2\u003C\/a\u003E.\u003Cbr \/\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003Cbr \/\u003ESeth Pettie received his Ph.D. in Computer Science from the University of Texas at Austin, in 2003.\u0026nbsp; From 2003-2006 he was an Alexander von Humboldt Postdoctoral Fellow at the Max Planck Institute for Computer Science, in Saarbruecken, Germany.\u0026nbsp; Since 2006 he has been a professor of Electrical Engineering and Computer Science at the University of Michigan, in Ann Arbor.\u003Cbr \/\u003E\u003C\/p\u003E\u003Cp\u003ESeth Pettie, Assoc. Prof. in Computer Science and Engineering University of Michigan, Ann Arbor \u003Ca href=\u0022http:\/\/web.eecs.umich.edu\/~pettie\u0022\u003Ehttp:\/\/web.eecs.umich.edu\/~pettie\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cbr \/\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Seth Pettie presents a talk as part of the ARC Colloquium series."}],"uid":"27255","created_gmt":"2014-11-26 14:43:54","changed_gmt":"2017-04-13 21:21:01","author":"Josie Giles","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-03-23T14:00:00-04:00","event_time_end":"2015-03-23T15:00:00-04:00","event_time_end_last":"2015-03-23T15:00:00-04:00","gmt_time_start":"2015-03-23 18:00:00","gmt_time_end":"2015-03-23 19:00:00","gmt_time_end_last":"2015-03-23 19:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"hg_media":{"349761":{"id":"349761","type":"image","title":"Seth Pettie","body":null,"created":"1449245696","gmt_created":"2015-12-04 16:14:56","changed":"1475895075","gmt_changed":"2016-10-08 02:51:15","alt":"Seth Pettie","file":{"fid":"201053","name":"seth-pettie.jpg","image_path":"\/sites\/default\/files\/images\/seth-pettie_0.jpg","image_full_path":"http:\/\/tlwarc.hg.gatech.edu\/\/sites\/default\/files\/images\/seth-pettie_0.jpg","mime":"image\/jpeg","size":575201,"path_740":"http:\/\/tlwarc.hg.gatech.edu\/sites\/default\/files\/styles\/740xx_scale\/public\/images\/seth-pettie_0.jpg?itok=OM07Mg-H"}}},"media_ids":["349761"],"related_links":[{"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":"9267","name":"ARC Colloquium"},{"id":"168003","name":"Seth Pettie"}],"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\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}