We consider the problem of List Update, one of the most fundamental problems in online algorithms. We are given a list of elements and requests for these elements that arrive over time. Our goal is to serve these requests, at a cost equivalent to their position in the list, with the option of moving them towards the head of the list. Sleator and Tarjan introduced the famous "Move to Front" algorithm (wherein any requested element is immediately moved to the head of the list) and showed that it is 2-competitive. While this bound is excellent, the absolute cost of the algorithm's solution may be very large (e.g., requesting the last half elements of the list would result in a solution cost that is quadratic in the length of the list). Thus, we consider the more general problem wherein every request arrives with a deadline and must be served, not immediately, but rather before the deadline. We further allow the algorithm to serve multiple requests simultaneously. We denote this problem as List Update with Time Windows. While this generalization benefits from lower solution costs, it requires new types of algorithms. In particular, for the simple example of requesting the last half elements of the list with overlapping time windows, Move-to-Front fails. We show an O(1) competitive algorithm. The algorithm is natural but the analysis is a bit complicated and a novel potential function is required. Thereafter we consider the more general problem of List Update with Delays in which the deadlines are replaced with arbitrary delay functions. This problem includes as a special case the prize collecting version in which a request might not be served (up to some deadline) and instead suffers an arbitrary given penalty. Here we also establish an O(1) competitive algorithm for general delays. The algorithm for the delay version is more complex and its analysis is significantly more involved.

We study the problem of learning a hierarchical tree representation of data from labeled samples, taken from an arbitrary (and possibly adversarial) distribution. Consider a collection of data tuples labeled according to their hierarchical structure. The smallest number of such tuples required in order to be able to accurately label subsequent tuples is of interest for data collection in machine learning. We present optimal sample complexity bounds for this problem in several learning settings, including (agnostic) PAC learning and online learning. Our results are based on tight bounds of the Natarajan and Littlestone dimensions of the associated problem. The corresponding tree classifiers can be constructed efficiently in near-linear time.

We present a new multi-layer peeling technique to cluster points in a metric space. A well-known non-parametric objective is to embed the metric space into a simpler structured metric space such as a line (i.e., Linear Arrangement) or a binary tree (i.e., Hierarchical Clustering). Points which are close in the metric space should be mapped to close points/leaves in the line/tree; similarly, points which are far in the metric space should be far in the line or on the tree. In particular we consider the Maximum Linear Arrangement problem \cite{Approximation_algorithms_for_maximum_linear_arrangement} and the Maximum Hierarchical Clustering problem \cite{Hierarchical_Clustering:_Objective_Functions_and_Algorithms} applied to metrics. We design approximation schemes ($1 - ε$ approximation for any constant $ε> 0$) for these objectives. In particular this shows that by considering metrics one may significantly improve former approximations ($0.5$ for Max Linear Arrangement and $0.74$ for Max Hierarchical Clustering). Our main technique, which is called multi-layer peeling, consists of recursively peeling off points which are far from the "core" of the metric space. The recursion ends once the core becomes a sufficiently densely weighted metric space (i.e. the average distance is at least a constant times the diameter) or once it becomes negligible with respect to its inner contribution to the objective. Interestingly, the algorithm in the Linear Arrangement case is much more involved than that in the Hierarchical Clustering case, and uses a significantly more delicate peeling.

Recently, Hierarchical Clustering (HC) has been considered through the lens of optimization. In particular, two maximization objectives have been defined. Moseley and Wang defined the \emph{Revenue} objective to handle similarity information given by a weighted graph on the data points (w.l.o.g., $[0,1]$ weights), while Cohen-Addad et al. defined the \emph{Dissimilarity} objective to handle dissimilarity information. In this paper, we prove structural lemmas for both objectives allowing us to convert any HC tree to a tree with constant number of internal nodes while incurring an arbitrarily small loss in each objective. Although the best-known approximations are 0.585 and 0.667 respectively, using our lemmas we obtain approximations arbitrarily close to 1, if not all weights are small (i.e., there exist constants $\epsilon, \delta$ such that the fraction of weights smaller than $\delta$, is at most $1 - \epsilon$); such instances encompass many metric-based similarity instances, thereby improving upon prior work. Finally, we introduce Hierarchical Correlation Clustering (HCC) to handle instances that contain similarity and dissimilarity information simultaneously. For HCC, we provide an approximation of 0.4767 and for complementary similarity/dissimilarity weights (analogous to $+/-$ correlation clustering), we again present nearly-optimal approximations.

We investigate the problem of hierarchically clustering data streams containing metric data in R^d. We introduce a desirable invariance property for such algorithms, describe a general family of hyperplane-based methods enjoying this property, and analyze two scalable instances of this general family against recently popularized similarity/dissimilarity-based metrics for hierarchical clustering. We prove a number of new results related to the approximation ratios of these algorithms, improving in various ways over the literature on this subject. Finally, since our algorithms are principled but also very practical, we carry out an experimental comparison on both synthetic and real-world datasets showing competitive results against known baselines.

We consider the problem of online min-cost perfect matching with concave delays. We begin with the single location variant. Specifically, requests arrive in an online fashion at a single location. The algorithm must then choose between matching a pair of requests or delaying them to be matched later on. The cost is defined by a concave function on the delay. Given linear or even convex delay functions, matching any two available requests is trivially optimal. However, this does not extend to concave delays. We solve this by providing an O(1)-competitive algorithm that is defined through a series of delay counters. Thereafter we consider the problem given an underlying n-points metric. The cost of a matching is then defined as the connection cost (as defined by the metric) plus the delay cost. Given linear delays, this problem was introduced by Emek et al. and dubbed the Min-cost perfect matching with linear delays (MPMD) problem. Liu et al. considered convex delays and subsequently asked whether there exists a solution with small competitive ratio given concave delays. We show this to be true by extending our single location algorithm and proving O(log n) competitiveness. Finally, we turn our focus to the bichromatic case, wherein requests have polarities and only opposite polarities may be matched. We show how to alter our former algorithms to again achieve O(1) and O(log n) competitiveness for the single location and for the metric case.

Hierarchical Clustering trees have been widely accepted as a useful form of clustering data, resulting in a prevalence of adopting fields including phylogenetics, image analysis, bioinformatics and more. Recently, Dasgupta (STOC 16’) initiated the analysis of these types of algorithms through the lenses of approximation. Later, the dual problem was considered by Moseley and Wang (NIPS 17’) dubbing it the Revenue goal function. In this problem, given a nonnegative weight $w_{ij}$ for each pair $i,j \in [n]=\{1,2, \ldots ,n\}$, the objective is to find a tree $T$ whose set of leaves is $[n]$ that maximizes the function $\sum_{i Cite this Paper BibTeX @InProceedings{pmlr-v125-alon20b, title = {Hierarchical Clustering: A 0.585 Revenue Approximation}, author = {Alon, Noga and Azar, Yossi and Vainstein, Danny}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {153--162}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/alon20b/alon20b.pdf}, url = {https://proceedings.mlr.press/v125/alon20b.html}, abstract = { Hierarchical Clustering trees have been widely accepted as a useful form of clustering data, resulting in a prevalence of adopting fields including phylogenetics, image analysis, bioinformatics and more. Recently, Dasgupta (STOC 16’) initiated the analysis of these types of algorithms through the lenses of approximation. Later, the dual problem was considered by Moseley and Wang (NIPS 17’) dubbing it the Revenue goal function. In this problem, given a nonnegative weight $w_{ij}$ for each pair $i,j \in [n]=\{1,2, \ldots ,n\}$, the objective is to find a tree $T$ whose set of leaves is $[n]$ that maximizes the function $\sum_{i Copy to Clipboard Download Endnote %0 Conference Paper %T Hierarchical Clustering: A 0.585 Revenue Approximation %A Noga Alon %A Yossi Azar %A Danny Vainstein %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-alon20b %I PMLR %P 153--162 %U https://proceedings.mlr.press/v125/alon20b.html %V 125 %X Hierarchical Clustering trees have been widely accepted as a useful form of clustering data, resulting in a prevalence of adopting fields including phylogenetics, image analysis, bioinformatics and more. Recently, Dasgupta (STOC 16’) initiated the analysis of these types of algorithms through the lenses of approximation. Later, the dual problem was considered by Moseley and Wang (NIPS 17’) dubbing it the Revenue goal function. In this problem, given a nonnegative weight $w_{ij}$ for each pair $i,j \in [n]=\{1,2, \ldots ,n\}$, the objective is to find a tree $T$ whose set of leaves is $[n]$ that maximizes the function $\sum_{i Copy to Clipboard Download APA Alon, N., Azar, Y. & Vainstein, D.. (2020). Hierarchical Clustering: A 0.585 Revenue Approximation. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:153-162 Available from https://proceedings.mlr.press/v125/alon20b.html. Copy to Clipboard Download Related Material Download PDF This site last compiled Sun, 05 Jul 2026 14:50:23 +0000 Github Account Copyright © The authors and PMLR 2026. MLResearchPress

One of the most significant algorithmic challenges in the "big data era" is handling instances that are too large to be processed by a single machine. The common practice in this regard is to partition the massive problem instance into smaller ones and process each one of them separately. In some cases, the solutions for the smaller instances are later on assembled into a solution for the whole instance, but in many cases this last stage cannot be pursued (e.g., because it is too costly, because of locality issues, or due to privacy considerations). Motivated by this phenomenon, we consider the following natural combinatorial question: Given a bin-packing instance (namely, a set of items with sizes in (0, 1] that should be packed into unit capacity bins) I and a partition Ii \ i of I into clusters, how large is the ratio ∑i Øpt(Ii) / Øpt(I), where Øpt(J) denotes the optimal number of bins into which the items in J can be packed? In this paper, we investigate the supremum of this ratio over all instances I and partitions Ii \ i, referred to as the bin-packing price of clustering (¶oC ). It is trivial to observe that if each cluster contains only one tiny item (and hence, Øpt(Ii) = 1), then the ¶oC is unbounded. On the other hand, a relatively straightforward argument shows that under the constraint that Øpt(Ii) ≥ 2, the ¶oC is 2. Our main challenge was to determine whether the ¶oC drops below 2 when Øpt(Ii) > 2. In addition, one may hope that łimk -> ∞ ¶oC(k) = 1, where ¶oC(k) denotes the ¶oC under the restriction to clusters Ii with Øpt(Ii) ≥ k. We resolve the former question affirmatively and the latter one negatively: Our main results are that ¶oC(k) łeq 1.951 for any k ≥ 3 and łimk -> ∞ ¶oC(k) = 1.691... Moreover, the former bound cannot be significantly improved as ¶oC(3) > 1.933. In addition to the immediate contribution of this combinatorial result to "big data" kind of applications, it turns out that it is useful also for an interesting online problem called bin-packing with delays.

We suggest a template that reveals the structure of many consensus algorithms as a generic procedure. The template builds on a new object, vacillate-adopt-commit which is an extension of the well known adopt-commit object. In addition we extend Aspnes's conciliator object to a new object that we call a reconciliator. The consensus algorithm template works in rounds of alternating vacillate-adopt-commit and reconciliator operations. The vacillate-adopt-commit object observes the processors' preferences and suggests a preference output with a measure of confidence vacillate, adopt or commit) on the preference. The reconciliator ensures termination, by providing new preferences for the processors. We show how several key consensus algorithms exactly fit our template. Here we demonstrate the decomposition of Ben-Or's randomized algorithm. The decomposition of the Phase King Byzantine and the Paxos algorithm are given in the full paper [1]. We analyze and compare our template based on vacillate-adopt-commit and reconciliator objects to previous work [3,5], suggesting a decomposition of consensus based on adopt-commit and conciliator objects. We claim that the three return values of vacillate-adopt-commit more accurately describe existing algorithms.

In this paper we focus on the Clairvoyant Dynamic Bin Packing (DBP) problem, which extends the classical online bin packing problem in that items arrive and depart over time and the departure time of an item is known upon its arrival. The problem naturally arises when handling cloud-based networks. We focus specifically on the MinUsageTime cost function which aims to minimize the overall usage time of all bins that are opened during the packing process. Earlier work has shown a O(\frac{\log \mu}{\log \log \mu}) upper bound where \mu is defined as the ratio between the maximal and minimal durations of all items. We improve the upper bound by giving an O(\sqrt{\log \mu})-competitive algorithm. We then provide a matching lower bound of \Omega(\sqrt{\log \mu}) on the competitive ratio of any online algorithm, thus closing the gap with regards to this problem. We then focus on what we call the class of aligned inputs and give a O(\log \log \mu)-competitive algorithm for this case, beating the lower bound of the general case by an exponential factor. Surprisingly enough, the analysis of our algorithm that we present, is closely related to various properties of binary strings.