Online resource allocation problems are central challenges in economics and computer science, modeling situations in which \(n\) items arriving one at a time must each be immediately allocated among agents. In such problems, our objective is to maximize a monotone reward function \(f(x)\) over the allocation vector \(x = (x_{ij})_{i,j}\), which describes the amount of each item given to each agent. In settings where \(f\) is concave and has “diminishing returns” (monotone decreasing gradient), several lines of work over the past two decades have had great success designing constant-competitive algorithms, including the foundational work of Mehta et al. (2005) on the Adwords problem and many follow-ups. Notably, via a greedy algorithm \(\frac{1}{2}\)-competitive in such settings, these works have shown that one can often obtain a competitive ratio of \(1 - \frac{1}{e} \approx 0.632\) in a variety of settings when items are divisible (i.e., allowing fractional allocations). However, prior works have thus far used a variety of problem-specific techniques, leaving open the general question: Does a \((1 - \frac{1}{e})\)-competitive fractional algorithm always exist for online resource allocation problems with concave, diminishing-returns objectives?

Most existing work in online stochastic combinatorial optimization assumes that inputs are drawn from independent distributions—a strong assumption that often fails in practice. At the other extreme, arbitrary correlations are equivalent to worst-case inputs via Yao’s minimax principle, making good algorithms often impossible. This motivates the study of intermediate models that capture mild correlations while still permitting nontrivial algorithms.

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

Online resource allocation is a rich and var-ied field. One of the most well-known problems in this area is online bipartite matching, introduced in 1990 by Karp, Vazirani, and Vazirani. Since then, many variants have been studied, including AdWords, the generalized assignment problem (GAP), and online submodular welfare maximization. In this paper, we introduce a generalization of GAP which we call the submodular assignment problem (SAP). This generalization captures many online assignment problems, including all classical online bipartite matching problems as well as broader online combinatorial optimization problems such as online arboricity, flow scheduling, and laminar restricted allocations. We present a fractional algorithm for online SAP that is$(1-1/e)$-competitive. Additionally, we study several integral special cases of the problem. In particular, we provide a$(1\ -1/e-\varepsilon){-}$competitive integral algorithm under a small-bids assumption, and a$(1\ -1/e)$-competitive integral algorithm for online submodular welfare maximization where the utility functions are given by rank functions of matroids. The key new ingredient for our results is the construction and structural analysis of a “water level” vector for polymatroids, which allows us to generalize the classic water-filling paradigm used in online matching problems. This construction reveals connections to submodular utility allocation markets and principal partition sequences of matroids.

Over the past two decades, significant strides have been made in stochastic problems such as revenue-optimal auction design and prophet inequalities, traditionally modeled with n independent random variables to represent the values of n items. However, in many applications, this assumption of independence often diverges from reality. Given the strong impossibility results associated with arbitrary correlations, recent research has pivoted towards exploring these problems under models of mild dependency.

Continuous submodular functions are a category of generally non-convex/non-concave functions with a wide spectrum of applications. The celebrated property of this class of functions - continuous submodularity - enables both exact minimization and approximate maximization in poly. time. Continuous submodularity is obtained by generalizing the notion of submodularity from discrete domains to continuous domains. It intuitively captures a repulsive effect amongst different dimensions of the defined multivariate function. In this paper, we systematically study continuous submodularity and a class of non-convex optimization problems: continuous submodular function maximization. We start by a thorough characterization of the class of continuous submodular functions, and show that continuous submodularity is equivalent to a weak version of the diminishing returns (DR) property. Thus we also derive a subclass of continuous submodular functions, termed continuous DR-submodular functions, which enjoys the full DR property. Then we present operations that preserve continuous (DR-)submodularity, thus yielding general rules for composing new submodular functions. We establish intriguing properties for the problem of constrained DR-submodular maximization, such as the local-global relation. We identify several applications of continuous submodular optimization, ranging from influence maximization, MAP inference for DPPs to provable mean field inference. For these applications, continuous submodularity formalizes valuable domain knowledge relevant for optimizing this class of objectives. We present inapproximability results and provable algorithms for two problem settings: constrained monotone DR-submodular maximization and constrained non-monotone DR-submodular maximization. Finally, we extensively evaluate the effectiveness of the proposed algorithms.