On the Complexity of Branching Proofs

We consider the task of proving integer infeasibility of a bounded convex set K in R^n using a general branching proof system. In a general branching proof, one constructs a branching tree by adding an integer disjunction at each node, such that the leaves of the tree correspond to empty sets (i.e., K together with … Read more

Linear Programming using Limited-Precision Oracles

Since the elimination algorithm of Fourier and Motzkin, many different methods have been developed for solving linear programs. When analyzing the time complexity of LP algorithms, it is typically either assumed that calculations are performed exactly and bounds are derived on the number of elementary arithmetic operations necessary, or the cost of all arithmetic operations … Read more