We present improved learning-augmented algorithms for the multi-option ski rental problem. Learning-augmented algorithms take machine learning (ML) predictions as an added part of the input and incorporate these predictions in solving the given problem. Due to their unique strength that combines the power of ML predictions with provable performance guarantees, they have been extensively studied in the context of online optimization problems. While the multi-option ski rental problem provides a natural generalization of the classical rent-or-buy variant, only deterministic algorithms for this problem were previously known, with or without learning augmentation. In this article, we first present that a very simple modification to a previously known algorithm suffices to give an improved deterministic learning-augmented algorithm. In fact, we prove that this algorithm has the best-possible performance of a deterministic algorithm by giving a matching lower bound. Then we present the first randomized learning-augmented algorithm, which surpasses the lower bound of deterministic algorithms; this learning-augmented algorithm is based on a new best-possible randomized competitive algorithm. These results are complemented by lower bounds for randomized competitive/learning-augmented algorithms.

We consider the classic correlation clustering problem in the hierarchical setting. Given a complete graph $G=(V, E)$ and $\ell$ layers of input information, where the input of each layer consists of a non-negative weight and a labeling of the edges with either + or -, this problem seeks to compute for each layer a partition of V such that the partition for any non-top layer subdivides the partition in the upper-layer and the weighted number of disagreements over the layers is minimized, where the disagreement of a layer is the number of + edges across parts plus the number of - edges within parts. Hierarchical correlation clustering is a natural formulation of the classic problem of fitting distances by ultrametrics, which is further known as numerical taxonomy [1]–[3] in the literature. While single-layer correlation clustering received wide attention since it was introduced in [4] and major progress evolved in the past three years [5]–[8], few is known for this problem in the hierarchical setting [9], [10]. The lack of understanding and adequate tools is reflected in the large approximation ratio known for this problem, which originates from 2021. In this work we make both conceptual and technical contributions towards the hierarchical clustering problem. We present a simple paradigm that greatly facilitates LP-rounding in hierarchical clustering, illustrated with a delicate algorithm providing a significantly improved approximation guarantee of 25.7846 for the hierarchical correlation clustering problem. Our techniques reveal surprising new properties and advances the current understanding for the formulation presented and subsequently used in [9] –[12] for hierarchical clustering over the past two decades. This provides a unifying interpretation on the core-technical problem in hierarchical clustering as the problem of finding cuts with prescribed properties regarding the average distance of certain cut pairs. We further illustrate this perspective by showing that a direct application of the paradigm and techniques presented in this work gives a simple alternative to the state-of-the-art result presented in [12] for the ultrametric violation distance problem. -hierarchical correlation clustering, ultrametric embedding, correlation clustering, linear programming rounding, approximation algorithms

Clustering is a fundamental task in both machine learning and data mining. Among various methods, edge-colored clustering (ECC) has emerged as a useful approach for handling categorical data. Given a hypergraph with (hyper)edges labeled by colors, ECC aims to assign vertex colors to minimize the number of edges where the vertex color differs from the edge's color. However, traditional ECC has inherent limitations, as it enforces a nonoverlapping and exhaustive clustering. To tackle these limitations, three versions of ECC have been studied: Local ECC and Global ECC, which allow overlapping clusters, and Robust ECC, which accounts for vertex outliers. For these problems, both linear programming (LP) rounding algorithms and greedy combinatorial algorithms have been proposed. While these LP-rounding algorithms provide high-quality solutions, they demand substantial computation time; the greedy algorithms, on the other hand, run very fast but often compromise solution quality. In this paper, we present a family of algorithms that combines the strengths of LP with the computational efficiency of combinatorial algorithms. Both experimental and theoretical analyses show that our algorithms efficiently produce high-quality solutions for all three problems: Local, Global, and Robust ECC. We complement our algorithmic contributions with complexity-theoretic inapproximability results and integrality gap bounds, which suggest that significant theoretical improvements are unlikely. Our results also answer two open questions previously raised in the literature.

In this paper, we present improved learning-augmented algorithms for the multi-option ski rental problem. Learning-augmented algorithms take ML predictions as an added part of the input and incorporates these predictions in solving the given problem. Due to their unique strength that combines the power of ML predictions with rigorous performance guarantees, they have been extensively studied in the context of online optimization problems. Even though ski rental problems are one of the canonical problems in the field of online optimization, only deterministic algorithms were previously known for multi-option ski rental, with or without learning augmentation. We present the first randomized learning-augmented algorithm for this problem, surpassing previous performance guarantees given by deterministic algorithms. Our learning-augmented algorithm is based on a new, provably best-possible randomized competitive algorithm for the problem. Our results are further complemented by lower bounds for deterministic and randomized algorithms, and computational experiments evaluating our algorithms' performance improvements.