The Weighted Tree Augmentation Problem (WTAP) is a fundamental network design problem where the goal is to find a minimum-cost set of additional edges (links) to make an input tree 2-edge-connected. While a 2-approximation is standard and the integrality gap of the classic Cut LP relaxation is known to be at least 1.5, achieving approximation factors significantly below 2 has proven challenging. Recent advances of Traub and Zenklusen using local search culminated in a ratio of 1.5+є, establishing the state-of-the-art. In this work, we present a randomized approximation algorithm for WTAP with an approximation ratio below 1.49. Our approach is based on designing and rounding a strong linear programming relaxation for WTAP which incorporates variables that represent subsets of edges and the links used to cover them, inspired by lift-and-project methods like Sherali-Adams.

In this paper, we consider a new problem of portfolio optimization using stochastic information. In a setting where there is some uncertainty, we ask how to best select k potential solutions, with the goal of optimizing the value of the best solution. More formally, given a combinatorial problem Π, a set of value functions 𝒱 over the solutions of Π, and a distribution 𝒟 over 𝒱, our goal is to select k solutions of Π that maximize or minimize the expected value of the best of those solutions. For a simple example, consider the classic knapsack problem: given a universe of elements each with unit weight and a positive value, the task is to select r elements maximizing the total value. Now suppose that each element’s weight comes from a (known) distribution. How should we select k different solutions so that one of them is likely to yield a high value? In this work, we tackle this basic problem, and generalize it to the setting where the underlying set system forms a matroid. On the technical side, it is clear that the candidate solutions we select must be diverse and anti-correlated; however, it is not clear how to do so efficiently. Our main result is a polynomial-time algorithm that constructs a portfolio within a constant factor of the optimal.

In recent years there has been a significant research effort on incorporating predictions into online algorithms. However, work in this area often makes the underlying assumption that predictions come for free (e.g., without any computational or monetary costs). In this paper, we consider a cost associated with making predictions. We show that interesting algorithmic subtleties arise for even the most basic online problems, such as ski rental and its generalization, the Bahncard problem. In particular, we show that with costly predictions, care needs to be taken in (i) asking for the prediction at the right time, (ii) deciding if it is worth asking for the prediction, and (iii) how many predictions we ask for, in settings where it is natural to consider making multiple predictions. Specifically, (i) in the basic ski-rental setting, we compute the optimal delay before asking the predictor, (ii) in the same setting, given apriori information about the true number of ski-days through its mean and variance, we provide a simple algorithm that is near-optimal, under some natural parameter settings, in deciding if it is worth asking for the predictor and (iii) in the setting of the Bahncard problem, we provide a $(1+\varepsilon)$-approximation algorithm and quantify lower bounds on the number of queries required to do so. In addition, we show that solving the problem optimally would require almost complete information of the instance.

This paper considers the classic Online Steiner Forest problem where one is given a (weighted) graph G and an arbitrary set of k terminal pairs {{s1, t1}, …, {sk, tk}} that are required to be connected. The goal is to maintain a minimum-weight sub-graph that satisfies all the connectivity requirements as the pairs are revealed one by one. It has been known for a long time that no algorithm (even randomized) can be better than Ω(log(k))-competitive for this problem. Interestingly, a simple greedy algorithm is already very efficient for this problem. This algorithm can be informally described as follows: Upon arrival of a new pair {si, ti}, connect si and ti with the shortest path in the current metric, contract the metric along the chosen path and wait for the next pair. Although simple and intuitive, greedy proved itself challenging to analyze and its competitive ratio is a longstanding open problem in the area of online algorithms. The last progress on this problem is due to an elegant analysis by Awerbuch, Azar, and Bartal [SODA 1996], who showed that greedy is O(log2(k))-competitive. In this paper, we identify a natural measure of the “efficiency” of greedy that we call the contraction. The contraction of a pair {si, ti} is the ratio between the distance dG (si, ti) in the graph G and the actual cost that greedy pays for connecting the pair {si, ti}. Intuitively, a worst-case instance should be an instance on which greedy is very “inefficient”, i.e. an instance for which all pairs have a relatively small contraction. Indeed, one can remark that all hard instances that appeared in the literature are such that all pairs have a contraction of exactly 1 (which is the smallest contraction possible). Our main result, among others, is to show that greedy is O(log(k) log log(k))-competitive on such instances. At the heart of this new result lies an original use of dual fitting, in which we use the dual solution not only to lower bound the optimum as it is usually the case in competitive analysis, but also to recursively partition the global instance into several disjoint instances of much smaller complexity.