{"71285":{"#nid":"71285","#data":{"type":"event","title":"ARC Colloquium: Ola Svensson,  \u00c9cole polytechnique f\u00e9d\u00e9rale de Lausanne EPFL","body":[{"value":"\u003Cp\u003E\u003Cbr \/\u003EWe present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a decreased cost.\u003C\/p\u003E\u003Cp\u003EFor the TSP on graphic metrics (graph-TSP), the approach yields a 1.461-approximation algorithm with respect to the Held-Karp lower bound. For graph-TSP restricted to a class of graphs that contains degree three bounded and claw-free graphs, we show that the integrality gap of the Held-Karp relaxation matches the conjectured ratio 4\/3. The framework allows for generalizations in a natural way and also leads to a 1.586-approximation algorithm for the traveling salesman path problem on graphic metrics where the start and end vertices are prespecified.\u003C\/p\u003E\u003Cp\u003EThis is joint work with Tobias Momke.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003E\u003Cbr \/\u003EWe present a framework for approximating the metric TSP based on a novel use of matchings.\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":[{"value":"Approximating Graphic TSP by Matchings"}],"uid":"27263","created_gmt":"2011-10-14 11:39:40","changed_gmt":"2016-10-08 01:56:19","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-10-19T14:30:00-04:00","event_time_end":"2011-10-19T14:30:00-04:00","event_time_end_last":"2011-10-19T14:30:00-04:00","gmt_time_start":"2011-10-19 18:30:00","gmt_time_end":"2011-10-19 18:30:00","gmt_time_end_last":"2011-10-19 18:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"14722","name":"approximation algorithm"},{"id":"14724","name":"claw-free graphs"},{"id":"14721","name":"graph-TSP"},{"id":"14723","name":"Held-Karp"},{"id":"14725","name":"traveling salesman path"}],"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":"\u003Cp\u003EPrasad Tetali\u003Cbr \/\u003EDirector, Algorithms Research Center\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}