In the correlation clustering problem, the input is a signed graph where the sign indicates whether pairs of nodes should be placed in the same cluster or not. The goal is to create a clustering that minimizes the number of disagreements with these signs. Correlation clustering is a key unsupervised learning problem with many practical applications. It has been widely studied in various settings, including versions with fairness constraints and cases where nodes arrive online. In this paper, we explore a problem that combines these two settings: nodes arrive online and reveal their membership in protected groups upon arrival. We are only allowed to output fair clusters, i.e., clusters where the representation of each protected group is upper bounded by a user-specified constant at the beginning of the arrival sequence. Our aim is to maintain approximately optimal fair clustering while minimizing a node’s worst-case recourse, i.e., the number of times it changes clusters. We present an algorithm that achieves worst-case logarithmic recourse per node while maintaining a constant-factor fair approximate clustering. Additionally, our approach simplifies the algorithm and analysis used in prior work by Cohen-Addad et al. (2022) in the online setting with recourse.

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.

We study the classic problem of correlation clustering in dynamic vertex streams. In this setting, vertices are either added or randomly deleted over time, and each vertex pair is connected by a positive or negative edge. The objective is to continuously find a partition which minimizes the sum of positive edges crossing clusters and negative edges within clusters. We present an algorithm that maintains an $O(1)$-approximation with $O(\text{polylog} n)$ amortized update time. Prior to our work Behnezhad et al. in SODA 2023 achieved a $5$-approximation with $O(1)$ expected update time in edge streams which translates in vertex streams to an $O(D)$-update time where $D$ is the maximum possible degree. Finally we complement our theoretical analysis with experiments on real world data.

Algorithms with predictions is a recent framework for decision-making under uncertainty that leverages the power of machine-learned predictions without making any assumption about their quality. The goal in this framework is for algorithms to achieve an improved performance when the predictions are accurate while maintaining acceptable guarantees when the predictions are erroneous. A serious concern with algorithms that use predictions is that these predictions can be biased and, as a result, cause the algorithm to make decisions that are deemed unfair. We show that this concern manifests itself in the classical secretary problem in the learning-augmented setting---the state-of-the-art algorithm can have zero probability of accepting the best candidate, which we deem unfair, despite promising to accept a candidate whose expected value is at least $\max\{\Omega (1) , 1 - O(\varepsilon)\}$ times the optimal value, where $\varepsilon$ is the prediction error. We show how to preserve this promise while also guaranteeing to accept the best candidate with probability $\Omega(1)$. Our algorithm and analysis are based on a new ``pegging'' idea that diverges from existing works and simplifies/unifies some of their results. Finally, we extend to the $k$-secretary problem and complement our theoretical analysis with experiments.

In the correlation clustering problem the input is a signed graph where the sign indicates whether each pair of points should be placed in the same cluster or not. The goal of the problem is to compute a clustering which minimizes the number of disagreements with such recommendation. Thanks to its many practical applications, correlation clustering is a fundamental unsupervised learning problem and has been extensively studied in many different settings. In this paper we study the problem in the classic online setting with recourse; The vertices of the graphs arrive in an online manner and the goal is to maintain an approximate clustering while minimizing the number of times each vertex changes cluster. Our main contribution is an algorithm that achieves logarithmic recourse per vertex in the worst case. We also complement this result with a tight lower bound. Finally we show experimentally that our algorithm achieves better performances than state-of-the-art algorithms on real world data.

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.

As power management has become a primary concern in modern data centers, computing resources are being scaled dynamically to minimize energy consumption. We initiate the study of a variant of the classic online speed scaling problem, in which machine learning predictions about the future can be integrated naturally. Inspired by recent work on learning-augmented online algorithms, we propose an algorithm which incorporates predictions in a black-box manner and outperforms any online algorithm if the accuracy is high, yet maintains provable guarantees if the prediction is very inaccurate. We provide both theoretical and experimental evidence to support our claims.

The extension of classical online algorithms when provided with predictions is a new and active research area. In this paper, we extend the primal-dual method for online algorithms in order to incorporate predictions that advise the online algorithm about the next action to take. We use this framework to obtain novel algorithms for a variety of online covering problems. We compare our algorithms to the cost of the true and predicted offline optimal solutions and show that these algorithms outperform any online algorithm when the prediction is accurate while maintaining good guarantees when the prediction is misleading.

The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertices arriving only on one side, and presented optimal deterministic and randomized algorithms for this setting. In comparison, more general arrival models, such as edge arrivals and general vertex arrivals, have proven more challenging and positive results are known only for various relaxations of the problem. In particular, even the basic question of whether randomization allows one to beat the trivially-optimal deterministic competitive ratio of 1/2 for either of these models was open. In this paper, we resolve this question for both these natural arrival models, and show the following.1) For edge arrivals, randomization does not help - no randomized algorithm is better than 1/2 competitive. 2)For general vertex arrivals, randomization helps - there exists a randomized (1/2+Ω(1)) -competitive online matching algorithm.