We consider a multiple-choice mixed packing and covering problem in the online setting: at each timestep \(t\), the algorithm faces a collection of \(K\) choices. Each choice consumes some resources, and gives some benefits; both resources and benefits are \(d\)-dimensional vectors. We would like to make a choice for each timestep, such that we use at most \(B\) units of each resource, and we get at least \(B\) units of each kind of benefit. Among its many applications, this general problem captures the question of load-balancing on unrelated machines, where the choices are allocations of jobs to machines.

Modern mixed-integer programming solvers use the branch-and-cut framework, where cutting planes are added to improve the tightness of the linear programming (LP) relaxation, with the expectation that the tighter formulation would produce smaller branch-and-bound trees. In this work, we consider the question of whether adding cuts will always lead to smaller trees for a given fixed branching rule. We formally call such a property of a branching rule monotonicity. We prove that any branching rule which exclusively branches on fractional variables in the LP solution is nonmonotonic. Moreover, we present a family of instances where adding a single cut leads to an exponential increase in the size of full strong branching trees, despite improving the LP bound. Finally, we empirically attempt to estimate the prevalence of nonmonotonicity in practice while using full strong branching. We consider randomly generated multidimensional knapsacks tightened by cover cuts as well as instances from the MIPLIB 2017 benchmark set for the computational experiments. Our main insight from these experiments is that if the gap closed by cuts is small, change in tree size is difficult to predict, and often increases, possibly due to inherent nonmonotonicity. However, when a sufficiently large gap is closed, a significant decrease in tree size may be expected. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This work was supported by Air Force Office of Scientific Research [Grant F9550-22-1-0052]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0709 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0709 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Online Set Cover and Load Balancing are central problems in online optimization, and there is a long line of work focusing on developing algorithms for these problems with convex objectives. Although we know optimal online algorithms with $\ell_{p}$-norm objectives, recent developments for general norms and convex objectives that rely on the online primal-dual framework apply only to fractional settings due to large integrality gaps. Our work focuses on directly designing integral online algorithms for Set Cover and Load Balancing with convex objectives, bypassing the convex-relaxation and the primal-dual technique. Some of the main implications of our approach are: 1) For Online Set Cover, we can extend the results of [1] for convex objectives and of [2] for symmetric norms from fractional to integral settings. 2) Our results for convex objectives and symmetric norms even apply to the Online Generalized Scheduling Problem, which generalizes both Set Cover and Load Balancing. Previous works could only handle the offline version of this problem with norm objectives [3]. 3) Our approach easily extends to settings involving disjointcomposition of norms. This allows us to recover or improve the norm-composition results of [4], [2] and extend our results to a large class of norms beyond the symmetric setting. Our approach involves first reducing these online problems to online packing problems, and to then design good approximation algorithms for the latter. To solve these packing problem, we use two key ideas. First, we decouple the global packing problem into a series of local packing problems on different machines. Second, we choose random activation thresholds for machines such that conditional on a machine being activated the expected number of jobs it covers is high compared to its cost. This approach may be of independent interest and could find applications to other online problems. Index Terms-online algorithms, set cover, load balancing

Given any algorithm for convex optimization that uses exact first-order information (i.e., function values and subgradients), we show how to use such an algorithm to solve the problem with access to inexact first-order information. This is done in a “black-box” manner without knowledge of the internal workings of the algorithm. This complements previous work that considers the performance of specific algorithms like (accelerated) gradient descent with inexact information. In particular, our results apply to a wider range of algorithms beyond variants of gradient descent, e.g., projection-free methods, cutting-plane methods, or any other first-order methods formulated in the future. Further, they also apply to algorithms that handle structured nonconvexities like mixed-integer decision variables.

Many classical problems in theoretical computer science involve norms, even if implicitly; for example, both XOS functions and downward-closed sets are equivalent to some norms. The last decade has seen a lot of interest in designing algorithms beyond the standard ℓp norms ||· ||p. Despite notable advancements, many existing methods remain tailored to specific problems, leaving a broader applicability to general norms less understood. This paper investigates the intrinsic properties of ℓp norms that facilitate their widespread use and seeks to abstract these qualities to a more general setting. We identify supermodularity—often reserved for combinatorial set functions and characterized by monotone gradients—as a defining feature beneficial for ||·||pp. We introduce the notion of p-supermodularity for norms, asserting that a norm is p-supermodular if its pth power function exhibits supermodularity. The association of supermodularity with norms offers a new lens through which to view and construct algorithms. Our work demonstrates that for a large class of problems p-supermodularity is a sufficient criterion for developing good algorithms. This is either by reframing existing algorithms for problems like Online Load-Balancing and Bandits with Knapsacks through a supermodular lens, or by introducing novel analyses for problems such as Online Covering, Online Packing, and Stochastic Probing. Moreover, we prove that every symmetric norm can be approximated by a p-supermodular norm. Together, these recover and extend several existing results, and support p-supermodularity as a unified theoretical framework for optimization challenges centered around norm-related problems.

Motivated by cloud computing applications, we study the problem of how to optimally deploy new hardware subject to both power and robustness constraints. To model the situation observed in large-scale data centers, we introduce the Online Demand Scheduling with Failover problem. There are m identical devices with capacity constraints. Demands come one-by-one and, to be robust against a device failure, need to be assigned to a pair of devices. When a device fails (in a failover scenario), each demand assigned to it is rerouted to its paired device (which may now run at increased capacity). The goal is to assign demands to the devices to maximize the total utilization subject to both the normal capacity constraints as well as these novel failover constraints. These latter constraints introduce new decision tradeoffs not present in classic assignment problems such as the Multiple Knapsack problem and AdWords. In the worst-case model, we design a deterministic ≈ 1/2-competitive algorithm, and show this is essentially tight. To circumvent this constant-factor loss, which represents substantial capital losses for big cloud providers, we consider the stochastic arrival model, where all demands come i.i.d. from an unknown distribution. In this model we design an algorithm that achieves sub-linear additive regret (i.e. as OPT or m increases, the multiplicative competitive ratio goes to 1). This requires a combination of different techniques, including a configuration LP with a non-trivial post-processing step and an online monotone matching procedure introduced by Rhee and Talagrand.

Vector norms play a fundamental role in computer science and optimization, so there is an ongoing effort to generalize existing algorithms to settings beyond ℓ∞ and ℓp norms. We show that many online and bandit applications for general norms admit good algorithms as long as the norm can be approximated by a function that is “gradient-stable”, a notion that we introduce. Roughly it says that the gradient of the function should not drastically decrease (multiplicatively) in any component as we increase the input vector. We prove that several families of norms, including all monotone symmetric norms, admit a gradient-stable approximation, giving us the first online and bandit algorithms for these norm families. In particular, our notion of gradient-stability gives O (log2 (dimension))-competitive algorithms for the symmetric norm generalizations of Online Generalized Load Balancing and Bandits with Knapsacks. Our techniques extend to applications beyond symmetric norms as well, e.g., to Online Vector Scheduling and to Online Generalized Assignment with Convex Costs. Some key properties underlying our applications that are implied by gradient-stable approximations are a “smooth game inequality” and an approximate converse to Jensen's inequality.

Decision trees are widely used in many settings where interpretable models are preferred or required. As confirmed by recent empirical studies, the interpretability/explanability of a decision tree critically depends on some of its structural parameters, like size and the average/maximum depth of its leaves. There is indeed a vast literature on the design and analysis of decision tree algorithms that aim at optimizing these parameters.This paper contributes to this important line of research: we propose as a novel criterion of measuring the interpretability of a decision tree, the sparsity of the set of attributes that are (on average) required to explain the classification of the examples. We give a tight characterization of the best possible guarantees achievable by a decision tree built to optimize both our newmeasure (which we call the {\em explanation size}) and the more classical measures of worst-case and average depth. In particular, we give an algorithm that guarantees $O(\ln n )$-approximation (hence optimal if $P \neq NP$) for the minimization of both the average/worst-case explanation size and the average/worst-case depth. In addition to our theoretical contributions, experiments with 20 real datasets show that our algorithm has accuracy competitive with CART while producing trees that allow for much simpler explanations.

We study the problem of solving Packing Integer Programs (PIPs) in the online setting, where columns in [0, 1]d of the constraint matrix are revealed sequentially, and the goal is to pick a subset of the columns that sum to at most B in each coordinate while maximizing the objective. Excellent results are known in the secretary setting, where the columns are adversarially chosen, but presented in a uniformly random order. However, these existing algorithms are susceptible to adversarial attacks: they try to “learn” characteristics of a good solution, but tend to over-fit to the model, and hence a small number of adversarial corruptions can cause the algorithm to fail. In this paper, we give the first robust algorithms for Packing Integer Programs, specifically in the recently proposed Byzantine Secretary framework [BGSZ20]. Our techniques are based on a two-level use of online learning, to robustly learn an approximation to the optimal value, and then to use this robust estimate to pick a good solution. These techniques are general and we use them to design robust algorithms for PIPs in the prophet model as well, specifically in the Prophet-with-Augmentations framework [ISW20]. We also improve known results in the Byzantine Secretary framework: we make the non-constructive results algorithmic and improve the existing bounds for single-item and matroid constraints.

Branch-and-bound is the workhorse of all state-of-the-art mixed integer linear programming (MILP) solvers. These implementations of branch-and-bound typically use variable branching, that is, the child nodes are obtained by fixing some variable to an integer value v in one node and to v+1 in the other node. Even though modern MILP solvers are able to solve very large-scale instances efficiently, relatively little attention has been given to understanding why the underlying branch-and-bound algorithm performs so well. In this paper our goal is to theoretically analyze the performance of the standard variable branching based branch-and-bound algorithm. In order to avoid the exponential worst-case lower bounds, we follow the common idea of considering random instances. More precisely, we consider random integer programs where the entries of the coefficient matrix and the objective function are randomly sampled. Our main result is that with good probability branch-and-bound with variable branching explores only a polynomial number of nodes to solve these instances, for a fixed number of constraints. To the best of our knowledge this is the first known such result for a standard version of branch-and-bound. We believe that this result provides a compelling indication of why branch-and-bound with variable branching works so well in practice.

The importance of primal-dual methods in online optimization can hardly be overstated, and they give several of the state-of-the art results in both of the most common models for online algorithms: the adversarial and the stochastic/random order models. Here we try to provide a more unified analysis of primal-dual algorithms to better understand the mechanisms behind this important method. With this we are able of recover and extend in one goal several results of the literature. In particular we obtain robust online algorithm for fairly general online convex problems: we consider the Mixed model where in some of the time steps the data is stochastic and in the others the data is adversarial. Both the quantity and location of the adversarial time steps are unknown to the algorithm. The guarantees of our algorithms interpolate between the (close to) best guarantees for each of the pure models. In particular, the presence of adversarial times does not degrade the guarantee relative to the stochastic part of the instance. More concretely, we first consider online convex programming: in each time step a feasible set Vt is revealed, and the algorithm needs to select vt ∊ Vt to minimize the total cost ψ (Σt vt), for a convex function ψ. Our robust primal-dual algorithm for this problem on the Mixed model recovers and extends, for example, a result of Gupta et al. [15] as well as the recent work on ℓp-norm load balancing [29]. We also consider the problem of welfare maximization with convex production costs: in each time a customer presents a value ct and resource consumption vector at, and the goal is to fractionally select customers to maximize the profit Σt ctxt – ψ(Σt atxt). Our robust primal-dual algorithm for this problem on the Mixed model recovers and extends the result of Azar et al. [3]. Given the ubiquity of primal-dual algorithms, we hope that the ideas of the analyses presented here will be useful in obtaining other robust algorithm in the Mixed or related models.

The random-order or secretary model is one of the most popular beyond-worst case model for online algorithms. While it avoids the pessimism of the traditional adversarial model, in practice we cannot expect the input to be presented in perfectly random order. This has motivated research on ``best of both worlds'' (algorithms with good performance on both purely stochastic and purely adversarial inputs), or even better, on inputs that are a mix of both stochastic and adversarial parts. Unfortunately the latter seems much harder to achieve and very few results of this type are known. Towards advancing our understanding of designing such robust algorithms, we propose a random-order model with bursts of adversarial time steps. The assumption of burstiness of unexpected patterns is reasonable in many contexts, since changes (e.g. spike in a demand for a good) are often triggered by a common external event. We then consider the Knapsack Secretary problem in this model: there is a knapsack of size $k$ (e.g., available quantity of a good), and in each of the $n$ time steps an item comes with its value and size in $[0,1]$ and the algorithm needs to make an irrevocable decision whether to accept or reject the item. We design an algorithm that gives an approximation of $1 - \tilde{O}(Γ/k)$ when the adversarial time steps can be covered by $Γ\ge \sqrt{k}$ intervals of size $\tilde{O}(\frac{n}{k})$. In particular, setting $Γ= \sqrt{k}$ gives a $(1 - O(\frac{\ln^2 k}{\sqrt{k}}))$-approximation that is resistant to up to a $\frac{\ln^2 k}{\sqrt{k}}$-fraction of the items being adversarial, which is almost optimal even in the absence of adversarial items. Also, setting $Γ= \tildeΩ(k)$ gives a constant approximation that is resistant to up to a constant fraction of items being adversarial.

Machine Teaching studies how efficiently a Teacher can guide a Learner to a target hypothesis. We focus on the model of Machine Teaching with a black box learner introduced in [Dasgupta et al., ICML 2019], where the teaching is done interactively without having any knowledge of the Learner’s algorithm and class of hypotheses, apart from the fact that it contains the target hypothesis $h^*$. We first refine some existing results for this model and, then, we study new variants of it. Motivated by the realistic possibility that $h^*$ is not available to the learner, we consider the case where the teacher can only aim at having the learner converge to a best available approximation of $h^*$. We also consider weaker black box learners, where, in each round, the choice of the consistent hypothesis returned to the Teacher is not adversarial, and in particular, we show that better provable bounds can be obtained for a type of Learner that moves to the next hypothesis smoothly, preferring hypotheses that are close to the current one; and for another type of Learner that can provide to the Teacher hypotheses chosen at random among those consistent with the examples received so far. Finally, we present an empirical evaluation of our basic interactive teacher on real datasets.

We consider the k-server problem on trees and HSTs. We give an algorithm based on Bregman projections. This algorithm has a competitive ratios that match some of the recent results given by Bubeck et al. (STOC 2018), whose algorithm was based on mirror-descent-based continuous dynamics prescribed via a differential inclusion.

This paper considers stochastic optimization problems whose objective functions involve powers of random variables. For a concrete example, consider the classic Stochastic ℓp Load Balancing Problem (StochLoadBalp): There are m machines and n jobs, and we are given independent random variables Yij describing the distribution of the load incurred on machine i if we assign job j to it. The goal is to assign each job to the machines in order to minimize the expected ℓp-norm of the total load incurred over the machines. That is, letting Ji denote the jobs assigned to machine i, we want to minimize . While convex relaxations represent one of the most powerful algorithmic tools, in problems such as StochLoadBalp the main difficulty is to capture such objective function in a way that only depends on each random variable separately. In this paper, show how to capture p-power-type objectives in such separable way by using the L-function method. This method was precisely introduced by Latala to capture in a sharp way the moment of sums of random variables through the individual marginals. We first show how this quickly leads to a constant-factor approximation for very general subset selection problem with p-moment objective. Moreover, we give a constant-factor approximation for StochLoadBalp, improving on the recent O(p/ ln p)-approximation of [Gupta et al., SODA 18]. Here the application of the method is much more involved. In particular, we need to prove structural results connecting the expected ℓp-norm of a random vector with the p-moments of its coordinate-marginals (machine loads) in a sharp way, taking into account simultaneously the different scales of the loads that are incurred in the different machines by an unknown assignment. Moreover, our starting convex (indeed linear) relaxation has exponentially many constraints that are not conducive to integral rounding; we need to use the solution of this LP to obtain a reduced LP which can then be used to obtain the desired assignment.

Suppose a set of requests arrives online: each request gives some value $v_i$ if accepted, but requires using some amount of each of $d$ resources. Our cost is a convex function of the vector of total utilization of these $d$ resources. Which requests should be accept to maximize our profit, i.e., the sum of values of the accepted demands, minus the convex cost? We consider this problem in the random-order a.k.a. secretary model, and show an $O(d)$-competitive algorithm for the case where the convex cost function is also supermodular. If the set of accepted demands must also be independent in a given matroid, we give an $O(d^3 α)$-competitive algorithm for the supermodular case, and an improved $O(d^2α)$ if the convex cost function is also separable. Here $α$ is the competitive ratio of the best algorithm for the submodular secretary problem. These extend and improve previous results known for this problem. Our techniques are simple but use powerful ideas from convex duality, which give clean interpretations of existing work, and allow us to give the extensions and improvements.

The problem of splitting attributes is one of the main steps in the construction of decision trees. In order to decide the best split, impurity measures such as Entropy and Gini are widely used. In practice, decision-tree inducers use heuristics for finding splits with small impurity when they consider nominal attributes with a large number of distinct values. However, there are no known guarantees for the quality of the splits obtained by these heuristics. To fill this gap, we propose two new splitting procedures that provably achieve near-optimal impurity. We also report experiments that provide evidence that the proposed methods are interesting candidates to be employed in splitting nominal attributes with many values during decision tree/random forest induction.

We consider the problem of online load balancing under ℓp-norms: sequential jobs need to be assigned to one of the machines and the goal is to minimize the ℓp-norm of the machine loads. This generalizes the classical problem of scheduling for makespan minimization (case and has been thoroughly studied. However, despite the recent push for beyond worst-case analyses, no such results are known for this problem. In this paper we provide algorithms with simultaneous guarantees for the worst-case model as well as for the random-order (i.e. secretary) model, where an arbitrary set of jobs comes in random order. First, we show that the greedy algorithm (with restart), known to have optimal O(p) worst-case guarantee, also has a (typically) improved random-order guarantee. However, the behavior of this algorithm in the random-order model degrades with p. We then propose algorithm SimultaneousLB that has simultaneously optimal guarantees (within constants) in both worst-case and random- order models. In particular, the random-order guarantee of SimultaneousLB improves as p increases. One of the main components is a new algorithm with improved regret for Online Linear Optimization (OLO) over the non-negative vectors in the ℓq ball. Interestingly, this OLO algorithm is also used to prove a purely probabilistic inequality that controls the correlations arising in the random-order model, a common source of difficulty for the analysis. Another important component used in both SimultaneousLB and our OLO algorithm is a smoothing of the ℓp-norm that may be of independent interest. This smoothness property allows us to see algorithm SimultaneousLB as essentially a greedy one in the worst-case model and as a primal-dual one in the random-order model, which is instrumental for its simultaneous guarantees.

A direct sum theorem for two parties and a function f states that the communication cost of solving k copies of f simultaneously with error probability 1/3 is at least k · R1/3(f), where R1/3(f) is the communication required to solve a single copy of f with error probability 1/3. We improve this for a natural family of functions f, showing that the 1-way communication required to solve k copies of f simultaneously with probability 2/3 is Ω(k · R1/k(f)). Since R1/k (f) may be as large as Ω(R1/3(f) · log k), we asymptotically beat the direct sum bound for such functions, showing that the trivial upper bound of solving each of the k copies of f with probability 1 − O(1/k) and taking a union bound is optimal! In order to achieve this, our direct sum involves a novel measure of information cost which allows a protocol to abort with constant probability, and otherwise must be correct with very high probability. Moreover, for the functions considered, we show strong lower bounds on the communication cost of protocols with these relaxed guarantees; indeed, our lower bounds match those for protocols that are not allowed to abort. In the distributed and streaming models, where one wants to be correct not only on a single query, but simultaneously on a sequence of n queries, we obtain optimal lower bounds on the communication or space complexity. Lower bounds obtained from our direct sum result show that a number of techniques in the sketching literature are optimal, including the following: (JL transform) Lower bound of on the dimension of (oblivious) Johnson-Lindenstrauss transforms. (ℓp-estimation) Lower bound for the size of encodings of n vectors in [±M]d that allow ℓ1 or ℓ2-estimation of . (Matrix sketching) Lower bound of on the dimension of a matrix sketch S satisfying the entrywise guarantee |(ASST B)i,j − (AB)i,j | ≤ ε‖Ai‖2‖Bj‖2. (Database joins) Lower bound of for sketching frequency vectors of n tables in a database, each with M records, in order to allow join size estimation.

In the stochastic knapsack problem, we are given a knapsack of size B, and a set of items whose sizes and rewards are drawn from a known probability distribution. To know the actual size and reward we have to schedule the item-when it completes, we get to know these values. The goal is to schedule the items (possibly making adaptive decisions based on the sizes seen so far) to maximize the expected total reward of items which successfully pack into the knapsack. We know constant-factor approximations when (i) the rewards and sizes are independent, and (ii) we cannot prematurely cancel items after we schedule them. What if either or both assumptions are relaxed? Related stochastic packing problems are the multi-armed bandit (and budgeted learning) problems, here one is given several arms which evolve in a specified stochastic fashion with each pull, and the goal is to (adaptively) decide which arms to pull, in order to maximize the expected reward obtained after B pulls in total. Much recent work on this problem focuses on the case when the evolution of each arm follows a martingale, i.e., when the expected reward from one pull of an arm is the same as the reward at the current state. What if the rewards do not form a martingale? In this paper, we give O(1)-approximation algorithms for the stochastic knapsack problem with correlations and/or cancellations. Extending the ideas developed here, we give O(1)-approximations for MAB problems without the martingale assumption. Indeed, we can show that previously proposed linear programming relaxations for these problems have large integrality gaps. So we propose new time-indexed LP relaxations, using a decomposition and "gap-filling" approach, we convert these fractional solutions to distributions over strategies, and then use the LP values and the time ordering information from these strategies to devise randomized adaptive scheduling algorithms.

Let G =( V,E ) be a graph representing a Web site, where nodes correspond to pages and arcs to hyperlinks. In this context, hotlinks are defined as shortcuts (new arcs) added to Web pages of G in order to reduce the time spent by users to reach their desired information. In this article, we consider the problem where G is a rooted directed tree and the goal is minimizing the expected time spent by users by assigning at most k hotlinks to each node. For the most studied version of this problem where at most one hotlink can be added to each node, we prove the existence of two FPTAS's which optimize different objectives considered in the literature: one minimizes the expected user path length and the other maximizes the expected reduction in user path lengths. These results improve over a constant factor approximation for the expected length and over a PTAS for the expected reduction, both obtained recently in Jacobs [2007]. Indeed, these FPTAS's are essentially the best possible results one can achieve under the assumption that P ≠ NP . Another contribution we give here is a 16-approximation algorithm for the most general version of the problem where up to k hotlinks can be assigned from each node. This algorithm runs in O (| V | log | V |) time and it turns to be the first algorithm with constant approximation for this problem.