{"671862":{"#nid":"671862","#data":{"type":"event","title":"ISyE Seminar - Bento Natura ","body":[{"value":"\u003Ch3\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E\u003C\/span\u003E\u003C\/span\u003E\u003Cspan\u003E\u003Cspan\u003E\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp;\u003C\/span\u003E\u003C\/span\u003E\u003C\/h3\u003E\r\n\r\n\u003Cp\u003E\u003Cspan\u003E\u003Cspan\u003ERecent Advances in Strongly Polynomial Algorithms for Linear Programming\u003C\/span\u003E\u003C\/span\u003E\u003C\/p\u003E\r\n\r\n\u003Ch3\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/h3\u003E\r\n\r\n\u003Cp\u003E\u003Cspan\u003E\u003Cspan\u003EWhereas ellipsoid methods and interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the simplex method that always admits an exponential bound.\u0026nbsp;\u003C\/span\u003E\u003C\/span\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cspan\u003E\u003Cspan\u003EAn important unresolved question in operations research, theoretical computer science, and related fields, concerns the existence of a strongly polynomial algorithm for linear programming. Such an algorithm\u0027s running time would solely depend on the problem\u0027s dimension and the number of constraints, independent of any additional condition numbers. This question, first articulated by Megiddo in the 1980s, has gained prominence as Smale\u0027s 9th problem.\u003C\/span\u003E\u003C\/span\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cspan\u003E\u003Cspan\u003EIn the first part of our talk, we introduce a new polynomial-time path-following interior point method where the number of iterations admits a combinatorial upper bound that is exponential in the number of constraints. More precisely, the iteration count of our algorithm is at most a small polynomial factor times the segment count of any piecewise linear trajectory within a wide neighborhood of the central path. Notably, it parallels the iteration count of any path-following interior point method, with an adjustment for this polynomial factor.\u003C\/span\u003E\u003C\/span\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cspan\u003E\u003Cspan\u003EIn the second part of our talk, we give a strongly polynomial algorithm for minimum cost generalized flow, and hence all linear programs with at most two nonzero entries per row, or at most two nonzero entries per column. This provides a next milestone towards answering Smale\u2019s 9th problem.\u003C\/span\u003E\u003C\/span\u003E\u003C\/p\u003E\r\n\r\n\u003Ch3\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/h3\u003E\r\n\r\n\u003Cp\u003E\u003Cspan\u003E\u003Cspan\u003EBento Natura is a Ronald J. and Carol T. Beerman\/ARC Postdoctoral Fellow in ISyE at Georgia Tech. He obtained his PhD in the Department of Mathematics at the London School of Economics, where he was supervised by L\u00e1szl\u00f3 V\u00e9gh. His doctoral thesis earned him the departmental Dissertation Prize and placed as a runner-up for the PhD Prize awarded by the OR Society of the United Kingdom. Prior to his PhD, Bento earned Bachelor\u0027s and Master\u0027s degrees in Mathematics from the University of Bonn, under the supervision of Stephan Held and Jens Vygen. Bento\u0027s current research interests are centered on algorithms, optimization, and game theory.\u003C\/span\u003E\u003C\/span\u003E\u003C\/p\u003E\r\n","summary":"","format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Ch3\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/h3\u003E\r\n\r\n\u003Cp\u003E\u003Cspan\u003E\u003Cspan\u003EWhereas ellipsoid methods and interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the simplex method that always admits an exponential bound.\u0026nbsp;\u003C\/span\u003E\u003C\/span\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cspan\u003E\u003Cspan\u003EAn important unresolved question in operations research, theoretical computer science, and related fields, concerns the existence of a strongly polynomial algorithm for linear programming. Such an algorithm\u0027s running time would solely depend on the problem\u0027s dimension and the number of constraints, independent of any additional condition numbers. This question, first articulated by Megiddo in the 1980s, has gained prominence as Smale\u0027s 9th problem.\u003C\/span\u003E\u003C\/span\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cspan\u003E\u003Cspan\u003EIn the first part of our talk, we introduce a new polynomial-time path-following interior point method where the number of iterations admits a combinatorial upper bound that is exponential in the number of constraints. More precisely, the iteration count of our algorithm is at most a small polynomial factor times the segment count of any piecewise linear trajectory within a wide neighborhood of the central path. Notably, it parallels the iteration count of any path-following interior point method, with an adjustment for this polynomial factor.\u003C\/span\u003E\u003C\/span\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cspan\u003E\u003Cspan\u003EIn the second part of our talk, we give a strongly polynomial algorithm for minimum cost generalized flow, and hence all linear programs with at most two nonzero entries per row, or at most two nonzero entries per column. This provides a next milestone towards answering Smale\u2019s 9th problem.\u003C\/span\u003E\u003C\/span\u003E\u003C\/p\u003E\r\n","format":"limited_html"}],"field_summary_sentence":[{"value":"Recent Advances in Strongly Polynomial Algorithms for Linear Programming"}],"uid":"34977","created_gmt":"2024-01-04 13:14:21","changed_gmt":"2024-01-04 13:14:21","author":"Julie Smith","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2024-01-18T11:00:00-05:00","event_time_end":"2024-01-18T12:00:00-05:00","event_time_end_last":"2024-01-18T12:00:00-05:00","gmt_time_start":"2024-01-18 16:00:00","gmt_time_end":"2024-01-18 17:00:00","gmt_time_end_last":"2024-01-18 17:00:00","rrule":null,"timezone":"America\/New_York"},"location":"ISyE Groseclose 402","extras":[],"groups":[{"id":"1242","name":"School of Industrial and Systems Engineering (ISYE)"}],"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":""}}}