diophantine approximation

On the Complexity of Branching Proofs

  • Daniel Dadush
  • Samarth Tiwari
    • Categories Integer Programming Tags , , , , ,

    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

  • Ambros Gleixner
  • Daniel E. Steffy
    • Categories Linear Programming, Optimization Software and Modeling Systems Tags , , , , , , ,

    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