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.

In this work, we prove new bounds on the additive gap between the value of a random integer program max cTx, Ax ≤ b, x ∈ {0,1}n with m constraints and that of its linear programming relaxation for a wide range of distributions on (A,b,c). Our investigation is motivated by the work of Dey, Dubey, and Molinaro (SODA'21), who gave a framework for relating the size of Branch-and-Bound (B&B) trees to additive integrality gaps. Dyer and Frieze (MOR '89) and Borst et al. (Mathematical Programming '22), respectively, showed that for certain random packing and Gaussian IPs, where the entries of A, c are independently distributed according to either the uniform distribution on [0,1] or the Gaussian distribution N(0,1), the integrality gap is bounded by Om(log2 n/n) with probability at least 1 − 1/n - e−Ωm(1). In this paper, we generalize these results to the cases where the entries of A are uniformly distributed on an integer interval (e.g., entries in {-1,0,1}), and where the columns of A are distributed according to an isotropic logconcave distribution. Second, we substantially improve the success probability to 1 - 1/poly(n), compared to constant probability in prior works (depending on m). Leveraging the connection to Branch-and-Bound, our gap results imply that for these IPs B&B trees have size npoly(m) with high probability (i.e., polynomial for fixed m), which significantly extends the class of IPs for which B&B is known to be polynomial. Our main technical contribution and the key to achieving the above results is a new linear discrepancy theorem for random matrices. Our theorem gives general conditions under which a target vector is equal to or very close to a {0,1} combination of the columns of a random matrix A. Compared to prior results, our theorem handles a much wider range of distributions on A, both continuous and discrete, and achieves success probability exponentially close to 1, as opposed to the constant probability shown in earlier results. Our proof uses a Fourier analytic approach, building on the work of Hoberg and Rothvoss (SODA '19) and Franks and Saks (RSA '20) who studied the discrepancy of random set systems and matrices respectively.

Abstract We study the problem of finding a temporal hybridization network containing at most k reticulations, for an input consisting of a set of phylogenetic trees. First, we introduce an FPT algorithm for the problem on an arbitrary set of m binary trees with n leaves each with a running time of $$O(5^k\cdot n\cdot m)$$ O ( 5 k · n · m ) . We also present the concept of temporal distance, which is a measure for how close a tree-child network is to being temporal. Then we introduce an algorithm for computing a tree-child network with temporal distance at most d and at most k reticulations in $$O((8k)^d5^ k\cdot k\cdot n\cdot m)$$ O ( ( 8 k ) d 5 k · k · n · m ) time. Lastly, we introduce an $$O(6^kk!\cdot k\cdot n^2)$$ O ( 6 k k ! · k · n 2 ) time algorithm for computing a temporal hybridization network for a set of two nonbinary trees. We also provide an implementation of all algorithms and an experimental analysis on their performance.

The theory of majorizing measures, extensively developed by Fernique, Talagrand and many others, provides one of the most general frameworks for controlling the behavior of stochastic processes. In particular, it can be applied to derive quantitative bounds on the expected suprema and the degree of continuity of sample paths for many processes. One of the crowning achievements of the theory is Talagrand’s tight alternative characterization of the suprema of Gaussian processes in terms of majorizing measures. The proof of this theorem was difficult, and thus considerable effort was put into the task of developing both shorter and easier to understand proofs. A major reason for this difficulty was considered to be theory of majorizing measures itself, which had the reputation of being opaque and mysterious. As a consequence, most recent treatments of the theory (including by Talagrand himself) have eschewed the use of majorizing measures in favor of a purely combinatorial approach (the generic chaining) where objects based on sequences of partitions provide roughly matching upper and lower bounds on the desired expected supremum. In this paper, we return to majorizing measures as a primary object of study, and give a viewpoint that we think is natural and clarifying from an optimization perspective. As our main contribution, we give an algorithmic proof of the majorizing measures theorem based on two parts: We make the simple (but apparently new) observation that finding the best majorizing measure can be cast as a convex program. This also allows for efficiently computing the measure using off-the-shelf methods from convex optimization. We obtain tree-based upper and lower bound certificates by rounding, in a series of steps, the primal and dual solutions to this convex program. While duality has conceptually been part of the theory since its beginnings, as far as we are aware no explicit link to convex optimization has been previously made.