We initiate a systematic study of utilizing predictions to improve over approximation guarantees of classic algorithms, without increasing the running time. We propose a generic method for a wide class of optimization problems that ask to select a feasible subset of input items of minimal (or maximal) total weight. This gives simple (near-)linear-time algorithms for, e.g., Vertex Cover, Steiner Tree, Minimum Weight Perfect Matching, Knapsack, and Maximum Clique. Our algorithms produce an optimal solution when provided with perfect predictions and their approximation ratio smoothly degrades with increasing prediction error. With small enough prediction error we achieve approximation guarantees that are beyond the reach without predictions in given time bounds, as exemplified by the NP-hardness and APX-hardness of many of the above problems. Although we show our approach to be optimal for this class of problems as a whole, there is a potential for exploiting specific structural properties of individual problems to obtain improved bounds; we demonstrate this on the Steiner Tree problem. We conclude with an empirical evaluation of our approach.

We propose a O (log k log n )-competitive randomized algorithm for online node-weighted Steiner forest. This is essentially optimal and significantly improves over the previous bound of O (log2 k log n ) by Hajiaghayi et al. [2017]. In fact, our result extends to the more general prize-collecting setting, improving over previous works by a poly-logarithmic factor. Our key technical contribution is a randomized online algorithm for set cover and non-metric facility location in a new adversarial model which we call semi-adaptive adversaries. As a by-product of our techniques, we obtain the first deterministic O (log |C| log |F|)-competitive algorithm for non-metric facility location.

Abstract We present algorithms for the $$(1+\epsilon )$$ ( 1 + ϵ ) -approximate version of the closest vector problem for certain norms. The currently fastest algorithm (Dadush and Kun 2016) for general norms in dimension n has running time of $$2^{O(n)}(1/\epsilon )^n$$ 2 O ( n ) ( 1 / ϵ ) n . We improve this substantially in the following two cases. First, for $$\ell _p$$ ℓ p -norms with $$p>2$$ p > 2 (resp. $$p \in [1,2]$$ p ∈ [ 1 , 2 ] ) fixed, we present an algorithm with a running time of $$2^{O(n)}(1+1/\epsilon )^{n/2}$$ 2 O ( n ) ( 1 + 1 / ϵ ) n / 2 (resp. $$2^{O(n)} (1+1/\epsilon )^{n/p}$$ 2 O ( n ) ( 1 + 1 / ϵ ) n / p ). This result is based on a geometric covering problem, that was introduced in the context of CVP by Eisenbrand et al.: How many convex bodies are needed to cover the ball of the norm such that, if scaled by factor 2 around their centroids, each one is contained in the $$(1+\epsilon )$$ ( 1 + ϵ ) -scaled homothet of the norm ball? We provide upper bounds for this $$(2,\epsilon )$$ ( 2 , ϵ ) -covering number by exploiting the modulus of smoothness of the $$\ell _p$$ ℓ

We consider the problem of solving integer programs of the form $\min \{\,c^\intercal x\ \colon\ Ax=b, x\geq 0\}$, where $A$ is a multistage stochastic matrix in the following sense: the primal treedepth of $A$ is bounded by a parameter $d$, which means that the columns of $A$ can be organized into a rooted forest of depth at most $d$ so that columns not bound by the ancestor/descendant relation in the forest do not have non-zero entries in the same row. We give an algorithm that solves this problem in fixed-parameter time $f(d,\|A\|_{\infty})\cdot n\log^{O(2^d)} n$, where $f$ is a computable function and $n$ is the number of rows of $A$. The algorithm works in the strong model, where the running time only measures unit arithmetic operations on the input numbers and does not depend on their bitlength. This is the first fpt algorithm for multistage stochastic integer programming to achieve almost linear running time in the strong sense. For the case of two-stage stochastic integer programs, our algorithm works in time $2^{(2\|A\|_\infty)^{O(r(r+s))}}\cdot n\log^{O(rs)} n$. The algorithm can be also parallelized: we give an implementation in the PRAM model that achieves running time $f(d,\|A\|_{\infty})\cdot \log^{O(2^d)} n$ using $n$ processors. The main conceptual ingredient in our algorithms is a new proximity result for multistage stochastic integer programs. We prove that if we consider an integer program $P$, say with a constraint matrix $A$, then for every optimum solution to the linear relaxation of $P$ there exists an optimum (integral) solution to $P$ that lies, in the $\ell_{\infty}$-norm, within distance bounded by a function of $\|A\|_{\infty}$ and the primal treedepth of $A$. On the way to achieve this result, we prove a generalization and considerable improvement of a structural result of Klein for multistage stochastic integer programs.

We show that a constant factor approximation of the shortest and closest lattice vector problem w.r.t. any 𝓁_p-norm can be computed in time 2^{(0.802 +ε) n}. This matches the currently fastest constant factor approximation algorithm for the shortest vector problem w.r.t. 𝓁₂. To obtain our result, we combine the latter algorithm w.r.t. 𝓁₂ with geometric insights related to coverings.