{"637712":{"#nid":"637712","#data":{"type":"event","title":"ARC Colloquium: Alberto Del Pia (WISC)","body":[{"value":"\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EAlberto Del Pia (WISC)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, October 19, 2020\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EVirtual via Bluejeans - 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003EShort simplex paths in lattice polytopes\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp; \u003C\/strong\u003EIn this talk we discuss the problem of designing a simplex algorithm for linear programs on lattice polytopes that traces \u0026lsquo;short\u0026rsquo; simplex paths from any given vertex to an optimal one. We consider a lattice polytope P contained in [0, k]^n and defined via m linear inequalities. Our first contribution is a simplex algorithm that reaches an optimal vertex by tracing a path along the edges of P of length in O(n^4 k log(nk)). The length of this path is independent on m and it is the best possible up to a polynomial function. In fact, it is only polynomially far from the worst-case diameter, which roughly grows as a linear function in n and k.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EMotivated by the fact that most known lattice polytopes are defined via 0,\u0026plusmn;1 constraint matrices, our second contribution is an iterative algorithm which exploits the largest absolute value \u0026alpha; of the entries in the constraint matrix. We show that the length of the simplex path generated by the iterative algorithm is in O(n^2 k log(nk\u0026alpha;)). In particular, if \u0026alpha; is bounded by a polynomial in n, k, then the length of the simplex path is in O(n^2 k log(nk)).\u003C\/p\u003E\r\n\r\n\u003Cp\u003EFor both algorithms, the number of arithmetic operations needed to compute the next vertex in the path is polynomial in n, m and log k. If k is polynomially bounded by n and m, the algorithm runs in strongly polynomial time.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/wid.wisc.edu\/people\/alberto-del-pia\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022http:\/\/arc.gatech.edu\/node\/121\u0022\u003Ehttp:\/\/arc.gatech.edu\/node\/121\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Short simplex paths in lattice polytopes: Virtual via Bluejeans at 11:00am"}],"uid":"27544","created_gmt":"2020-08-10 13:46:07","changed_gmt":"2020-08-26 13:52:53","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2020-10-19T12:00:00-04:00","event_time_end":"2020-10-19T13:00:00-04:00","event_time_end_last":"2020-10-19T13:00:00-04:00","gmt_time_start":"2020-10-19 16:00:00","gmt_time_end":"2020-10-19 17:00:00","gmt_time_end_last":"2020-10-19 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}