We consider the fundamental problem of allocating T indivisible items that arrive over time to n agents with additive preferences, with the goal of minimizing envy. This problem is tightly connected to the online multicolor discrepancy problem: vectors v1,...,vT ∈ ℝd with ||vi||2 ≤ 1 arrive online and must be, immediately and irrevocably, assigned to one of n colors to minimize [EQUATION] at each step, where Sℓ is the set of vectors having color ℓ. The special case of n = 2 is called online vector balancing. It is known that envy minimization reduces to multicolor discrepancy minimization. For an adaptive adversary, both problems have the same optimal bound: [EQUATION]; it is not known, however, whether this matches for weaker adversaries. Against an oblivious adversary, Alweiss et al. [2021] give a bound of O (log T), with high probability, for online multicolor discrepancy. Recently, Kulkarni et al. [2024] improve this to a tight [EQUATION] bound for online vector balancing. However, it has remained an open problem whether a [EQUATION] bound is possible for multicolor discrepancy. Furthermore, these results imply the state-of-the-art upper bounds for online envy minimization (for an oblivious adversary) for n and two agents, respectively; it is open whether better bounds are possible. We resolve all the aforementioned open problems. We establish that online envy minimization is, in fact, equivalent to online multicolor discrepancy for oblivious adversary: we give an [EQUATION] bound, for multicolor discrepancy, and a lower bound of [EQUATION] for envy minimization, resolving both problems. For weaker adversaries we prove that the two problems are no longer equivalent. Against an i.i.d. adversary, for online vector balancing, we give a [EQUATION] lower bound, while for envy minimization, we give an algorithm that guarantees a constant upper bound. Full version: https://arxiv.org/abs/2502.14624.

How well can we predict which posts on social media platforms will eventually become popular? What approaches should we use to accomplish this task? In an era where human attention has become a commodity, the early detection of trending posts in online social media platforms is a problem of special importance, with applications ranging from business marketing to political campaigns and beyond. In this work we provide new insight towards tackling this problem by performing in-depth experiments on discovering trending posts on the popular mixed-media microblogging platform Tumblr. Inspired by prior art, our approach involves examining the key traits of the early adopters of online posts and utilizes a variety of network and temporal features to assist in performing classification. We obtain the complete data coverage of Tumblr for two consecutive months in order to study the characteristics and emerging patterns of popular posts. Based on the data, we investigate the interplay between the observation window of early adopters, the performance of individual classifiers, and the importance of various features. We find consistent trends where the importance of network features increases as the observation window increases, while the importance of content and temporal features decreases. To the best of our knowledge, this work is the first attempt to carry out a large-scale study on the early detection of trending posts on Tumblr.

The Islamic State of Iraq and Syria (ISIS) is a extremist militant group in the Middle East known to employ social media for propaganda and recruiting purposes. In particular, the social media website Twitter is well known to be exploited by ISIS supporters. To this end, we devise an effective and scalable classification scheme to filter out ISIS propaganda accounts from the rest of the Twitter accounts covering the general population in specific geographic regions. We take a data-driven approach to train and test a classifier using a combination of both content-based and network-based features on a large-scale dataset consisting of 10% random sample of all public Twitter posts in 2014. Such a dataset contains a total of 4,820 confirmed ISIS propaganda accounts and a large collection of general user accounts originated in nearby Egypt and Saudi Arabia regions. We show that high precision and specificity is obtained with the proposed classifier through cross-validation. In addition, we demonstrate that the use of network-based features derived from the Twitter @mention network is crucial on accurte classification of ISIS propaganda accounts.