BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Faster algorithms for line search in the submodular base polytope Ene, Alina


We consider the line search problem in the base polytope of a submodular function: given a submodular function f and a direction a, the goal is to find the maximum value t such that f - t * a is non-negative. Recently, Gupta et al. [ICPO 2017] showed that the discrete Newton algorithm solves this problem using n^2 submodular function minimizations. In this talk, we present a faster algorithm for the problem. The talk is based on joint work with Huy Nguyen (Northeastern University) and Laszlo Vegh (London School of Economics).

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International