Decomposable Submodular Function Minimization: Discrete and Continuous
Alina Ene, Huy L. Nguyen, László A. Végh This paper investigates connections between discrete and continuous approaches for decomposable submodular function minimization. We provide improved running time estimates for the state-of-the-art continuous algorithms for the problem using combinatorial arguments. We also provide a systematic experimental comparison of the two types of methods, based on a clear distinction between level-0 and level-1 algorithms. |
arXiv:1703.01830 |

Rescaling Algorithms for Linear Programming
Part I: Conic feasibility Daniel Dadush, László A. Végh, Giacomo Zambelli Partly based on IPCO 2016 paper.
We propose simple polynomial-time algorithms for two linear conic
feasibility problems. For a matrix A, the kernel problem requires a
positive vector in the kernel of A, and the image problem requires a
positive vector in the image of A |
arXiv:1611.06427 |

A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization
Neil Olver, László A. Végh Accepted to STOC 2017.
We present a new strongly polynomial algorithm for generalized flow
maximization. The first strongly polynomial algorithm for this
problem was given in [Végh16]; our new algorithm is much
simpler, and much faster. The complexity bound O((m+n log n)mnlog(n |
arXiv:1611.01778 |

Submodular Search is Scheduling
Robbert Fokkink, Thomas Lidbetter, László A. Végh Suppose an object is hidden according to a known probability distribution in a finite set S of hiding places which must be examined in some order. The cost of searching subsets of S is given by a submodular function and we seek an ordering of S that finds the object in minimal expected cost. This problem is NP-hard and generalizes known search problems as well as the scheduling problem 1|prec|∑w_j g(C_j) where a set of jobs with weights and precedence constraints must be ordered to minimize the weighted sum of some concave function g of the completion times. Our main result is an efficient combinatorial 2-approximation algorithm for the problem, generalizing analogous results in scheduling theory. |
arXiv:1607.07598 |

Constant Factor Approximation for ATSP with Two Edge Weights
Ola Svensson, Jakub Tarnawski, László A. Végh IPCO 2016 We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. This builds on previous work of Svensson for unit edge weights; we solve the Local-Connectivity ATSP for two different edge weights using a flow decomposition theorem. |
arXiv:1511.07038 |

A 7/3-Approximation for Feedback Vertex Sets in Tournaments
Matthias Mnich, Virginia Vassilevska Williams, László A. Végh ESA 2016 We present a 7/3 approximation algorithm for finding a minimum weight feedback vertex set in a tournament. This improves the current best ratio 5/2, due to Cai et al. from 1998. |
PDF
arXiv:1511.01137 |

Approximating Minimum Cost Connectivity Orientation and Augmentation
Mohit Singh, László A. Végh SODA 2014 We investigate minimum cost combined connectivity augmentation and orientation problems. In particular, we give a 6-approximation for finding a minimum cost subgraph of an undirected graph that admits a (k,l)-edge-connected orientation. |
arXiv:1307.4164 |