9:30  10:20 
Bento Natura – A strongly polynomial algorithm for linear programs with at most two nonzero entries per row or column
We give a strongly polynomial algorithm for minimum cost generalized flow, and hence for optimizing any linear program with at most two nonzero entries per row, or at most two nonzero entries per column. Primal and dual feasibility were shown by Megiddo (SICOMP ’83) and Végh (MOR ’17) respectively. Our result can be viewed as progress towards understanding whether all linear programs can be solved in strongly polynomial time, also referred to as Smale’s 9th problem. Our approach is based on the recent primal dual interior point method (IPM) due to Allamigeon, Dadush, Loho, Natura and Végh (FOCS ’22). The number of iterations needed by the IPM is bounded, up to a polynomial factor in the number of inequalities, by the straight line complexity of the central path. Roughly speaking, this is the minimum number of pieces of any piecewise linear curve that multiplicatively approximates the central path. As our main contribution, we show that the straight line complexity of any minimum cost generalized flow instance is polynomial in the number of arcs and vertices. By applying a reduction of Hochbaum (ORL ’04), the same bound applies to any linear program with at most two nonzeros per column or per row. To be able to run the IPM, one requires a suitable initial point. For this purpose, we develop a novel multistage approach, where each stage can be solved in strongly polynomial time given the result of the previous stage. Beyond this, substantial work is needed to ensure that the bit complexity of each iterate remains bounded during the execution of the algorithm. For this purpose, we show that one can maintain a representation of the iterates as a low complexity convex combination of vertices. Our approach is blackbox and can be applied to any logbarrier path following method. Joint work with Daniel Dadush, Zhuan Khye Koh, Neil Olver, and László Végh.
(slides)

10:45  11:20 
Maryam Daryalal – Reasoning in Description Logic: A Mixedinteger Programming Framework
Description Logics (DL) are formal languages for knowledge representation, enabling structured ontology creation and logical reasoning. This talk presents an optimizationbased framework for enhancing reasoning in DL by employing mixedinteger programming methods. The framework exploits a novel approach of mapping DL axioms to a set of inequalities, enabling the use of advanced optimization techniques. The integration of column generation and branchandprice algorithms addresses the complexity of the resulting inequality system, offering a scalable solution for handling large ontological datasets. In a preliminary set of experiments, the framework's performance is evidenced by its application to the ontology of the Canadian Parliament, where it outperforms traditional reasoning methods. This work could mark a significant advancement for the Semantic Web community by merging ontology reasoning with sophisticated optimization methods to meet the challenges of semantic data processing.
(slides)
