A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
Ola Svensson, Jakub Tarnawski, László A. Végh

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem.

Decomposable Submodular Function Minimization: Discrete and Continuous
Alina Ene, Huy L. Nguyen, László A. Végh
Accepted to NIPS 2017.

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.

Geometric Rescaling Algorithms for Submodular Function Minimization
Daniel Dadush, László A. Végh, Giacomo Zambelli

We present a new class of polynomial-time algorithms for submodular function minimization (SFM), as well as a unified framework to obtain strongly polynomial SFM algorithms.

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 AT. Both algorithms iterate between simple first order steps and rescaling steps. These rescalings steps improve natural geometric potentials in the domain and image spaces, respectively. We also extend our algorithms for finding maximum support nonnegative vectors in the kernel of A and in the image of AT. The standard linear programming feasibility problem can be easily reduced to either maximum support problems, yielding polynomial-time algorithms for Linear Programming.

A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization
Neil Olver, László A. Végh
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(n2/m)) improves on the previous estimate in [Végh16] by almost a factor O(n2). Even for small numerical parameter values, our algorithm is essentially as fast as the best weakly polynomial algorithms. The key new technical idea is relaxing primal feasibility conditions. This allows us to work almost exclusively with integral flows, in contrast to all previous algorithms for the problem.

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.

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.

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.