BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Amitabh Basu (Johns Hopkins University)
DTSTART:20210526T150000Z
DTEND:20210526T153000Z
DTSTAMP:20260415T000130Z
UID:MIP2021/12
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/MIP2021/12/"
 >Complexity of cutting plane and branch-and-bound algorithms</a>\nby Amita
 bh Basu (Johns Hopkins University) as part of Mixed Integer Programming Wo
 rkshop 2021\n\n\nAbstract\nWe discuss the complexity of the two main ingre
 dients in integer optimization algorithms: cutting planes and branch-and-b
 ound. We prove upper and lower bounds on the efficiency of these algorithm
 s\, when efficiency is measured in terms of complexity of the LPs that are
  solved. More precisely\, we focus on the sparsity of the LPs and the numb
 er of LPs as measures of complexity. We also give general conditions under
  which combining branching and cutting into a branch-and-cut algorithm can
  do exponentially better than pure cutting planes or pure branch-and-bound
 . Time permitting\, some connections to mathematical logic and proof compl
 exity will be discussed.\n
LOCATION:https://researchseminars.org/talk/MIP2021/12/
END:VEVENT
END:VCALENDAR