Continuous Methods for Combinatorial Optimization – COMCOPT

Discrete optimization problems such as maximum flow or minimum cost flow represent the backbone of Computer Science - they constitute fundamental primitives for more complicated algorithms which are implemented in modern day computer systems. Nowadays, the size of the data collected and fed into the deployed implementations grows at an extremely fast rate, rendering many of the textbook algorithms intractable for practical purposes. We propose to address this issue by designing faster algorithms for a host of fundamental problems involving graph and submodular optimization. We do so by resorting to continuous time techniques commonly used in machine learning and scientific computing. The proposed algorithmic innovations are based on developing a set of customized interior point methods which heavily leverage the underlying combinatorial structure of the problems.