The weighted \(k\)-server is a variant of the \(k\)-server problem, where the cost of moving a server is the server’s weight times the distance through which it moves. The problem is famous for its intriguing properties and for evading standard techniques for designing and analyzing online algorithms. Even on uniform metric spaces with sufficiently many points, the deterministic competitive ratio of weighted \(k\)-server is known to increase doubly exponentially with respect to \(k\), while the behavior of its randomized competitive ratio is not fully understood. Specifically, no upper bound better than doubly exponential is known, while the best known lower bound is singly exponential in \(k\). In this paper, we close the exponential gap between these bounds by giving an \(\exp(\mathcal O(k^2))\)-competitive randomized online algorithm for the weighted \(k\)-server problem on uniform metrics, thus breaking the doubly exponential barrier for deterministic algorithms for the first time. This is achieved by a recursively defined notion of a phase which, on the one hand, forces a lower bound on the cost of any offline solution, while, on the other hand, also admits a randomized online algorithm with bounded expected cost. The algorithm is also recursive; it involves running several algorithms virtually and in parallel and following the decisions of one of them in a random order. We also show that our techniques can be lifted to construct an \(\exp(\mathcal O(k^2))\)-competitive randomized online algorithm for the generalized \(k\)-server problem on weighted uniform metrics.

In the prophet inequality problem, a gambler faces a sequence of items arriving online with values drawn independently from known distributions. On seeing an item, the gambler must choose whether to accept its value as her reward and quit the game, or reject it and continue. The gambler's aim is to maximize her expected reward relative to the expected maximum of the values of all items. Since the seventies, a tight bound of 1/2 has been known for this competitive ratio in the setting where the items arrive in an adversarial order [Krengel and Sucheston, 1977, 1978]. However, the optimum ratio still remains unknown in the order selection setting, where the gambler selects the arrival order, as well as in prophet secretary, where the items arrive in a random order. Moreover, it is not even known whether a separation exists between the two settings.

Motivated by fairness requirements in communication networks, we introduce a natural variant of the online paging problem, called min-max paging, where the objective is to minimize the maximum number of faults on any page. While the classical paging problem, whose objective is to minimize the total number of faults, admits k-competitive deterministic and O(log k)-competitive randomized algorithms, we show that min-max paging does not admit a c(k)-competitive algorithm for any function c. Specifically, we prove that the randomized competitive ratio of min-max paging is Ω(log(n)) and its deterministic competitive ratio is Ω(k log(n)/log(k)), where n is the total number of pages ever requested. We design a fractional algorithm for paging with a more general objective - minimize the value of an n-variate differentiable convex function applied to the vector of the number of faults on each page. This gives an O(log(n) log(k))-competitive fractional algorithm for min-max paging. We show how to round such a fractional algorithm with at most a k factor loss in the competitive ratio, resulting in a deterministic O(k log(n) log(k))-competitive algorithm for min-max paging. This matches our lower bound modulo a poly(log(k)) factor. We also give a randomized rounding algorithm that results in a O(log2 n log k)-competitive algorithm.

In this paper we introduce and study the STREAMINGCYCLES problem, a random order streaming version of the Boolean Hidden Hypermatching problem that has been instrumental in streaming lower bounds over the past decade. In this problem the edges of a graph G, comprising n/$\ell$ disjoint length-$\ell$ cycles on n vertices, are partitioned randomly among n players. Every edge is annotated with an independent uniformly random bit, and the players’ task is to output, for some cycle in G, the sum (modulo 2) of the bits on its edges, after one round of sequential communication.Our main result is an $\ell^{\Omega(\ell)}$ lower bound on the communication complexity of STREAMINGCYCLES, which is tight up to constant factors in the exponent. Applications of our lower bound for STREAMINGCYCLES include an essentially tight lower bound for component collection in (almost) random order graph streams, making progress towards a conjecture of Peng and Sohler [SODA’18] and the first exponential space lower bounds for random walk generation.

The weighted $k$-server problem is a natural generalization of the $k$-server problem in which the cost incurred in moving a server is the distance traveled times the weight of the server. Even after almost three decades since the seminal work of Fiat and Ricklin (1994), the competitive ratio of this problem remains poorly understood, even on the simplest class of metric spaces -- the uniform metric spaces. In particular, in the case of randomized algorithms against the oblivious adversary, neither a better upper bound that the doubly exponential deterministic upper bound, nor a better lower bound than the logarithmic lower bound of unweighted $k$-server, is known. In this article, we make significant progress towards understanding the randomized competitive ratio of weighted $k$-server on uniform metrics. We cut down the triply exponential gap between the upper and lower bound to a singly exponential gap by proving that the competitive ratio is at least exponential in $k$, substantially improving on the previously known lower bound of about $\ln k$.

In most online problems with delay, clairvoyance (i.e. knowing the future delay of a request upon its arrival) is required for polylogarithmic competitiveness. In this paper, we show that this is not the case for set cover with delay (SCD) - specifically, we present the first non-clairvoyant algorithm, which is O(log n log m)-competitive, where n is the number of elements and m is the number of sets. This matches the best known result for the classic online set cover (a special case of non-clairvoyant SCD). Moreover, clairvoyance does not allow for significant improvement - we present lower bounds of Ω(√{log n}) and Ω(√{log m}) for SCD which apply for the clairvoyant case. In addition, the competitiveness of our algorithm does not depend on the number of requests. Such a guarantee on the size of the universe alone was not previously known even for the clairvoyant case - the only previously-known algorithm (due to Carrasco et al.) is clairvoyant, with competitiveness that grows with the number of requests. For the special case of vertex cover with delay, we show a simpler, deterministic algorithm which is 3-competitive (and also non-clairvoyant).

Fueled by massive data, important decision making is being automated with the help of algorithms, therefore, fairness in algorithms has become an especially important research topic. In this work, we design new streaming and distributed algorithms for the fair k-center problem that models fair data summarization. The streaming and distributed models of computation have an attractive feature of being able to handle massive data sets that do not fit into main memory. Our main contributions are: (a) the first distributed algorithm; which has provably constant approximation ratio and is extremely parallelizable, and (b) a two-pass streaming algorithm with a provable approximation guarantee matching the best known algorithm (which is not a streaming algorithm). Our algorithms have the advantages of being easy to implement in practice, being fast with linear running times, having very small working memory and communication, and outperforming existing algorithms on several real and synthetic data sets. To complement our distributed algorithm, we also give a hardness result for natural distributed algorithms, which holds for even the special case of k-center.

The weighted k -server problem is a generalization of the k -server problem wherein the cost of moving a server of weight β i through a distance d is β i ⋅ d . On uniform metric spaces, this models caching with caches having different page replacement costs. A memoryless algorithm is an online algorithm whose behavior is independent of the history given the positions of its k servers. In this article, we develop a framework to analyze the competitiveness of randomized memoryless algorithms. The key technical contribution is a method for working with potential functions defined implicitly as the solution of a linear system. Using this, we establish tight bounds on the competitive ratio achievable by randomized memoryless algorithms for the weighted k -server problem on uniform metrics. We first prove that there is an α k -competitive memoryless algorithm for this problem, where α k =α k − 1 2 + 3α k − 1 +1; α 1 = 1. We complement this result by proving that no randomized memoryless algorithm can have a competitive ratio less than α k . Finally, we prove that the above bounds also hold for the generalized k -server problem on weighted uniform metrics.

We consider the problem of testing graph cluster structure: given access to a graph G = (V, E), can we quickly determine whether the graph can be partitioned into a few clusters with good inner conductance, or is far from any such graph? This is a generalization of the well-studied problem of testing graph expansion, where one wants to distinguish between the graph having good expansion (i.e. being a good single cluster) and the graph having a sparse cut (i.e. being a union of at least two clusters). A recent work of Czumaj, Peng, and Sohler (STOC'15) gave an ingenious sublinear time algorithm for testing k-clusterability in time Õ(n^1/2 poly(k)). Their algorithm implicitly embeds a random sample of vertices of the graph into Euclidean space, and then clusters the samples based on estimates of Euclidean distances between the points. This yields a very efficient testing algorithm, but only works if the cluster structure is very strong: it is necessary to assume that the gap between conductances of accepted and rejected graphs is at least logarithmic in the size of the graph G. In this paper we show how one can leverage more refined geometric information, namely angles as opposed to distances, to obtain a sublinear time tester that works even when the gap is a sufficiently large constant. Our tester is based on the singular value decomposition of a natural matrix derived from random walk transition probabilities from a small sample of seed nodes. We complement our algorithm with a matching lower bound on the query complexity of testing clusterability. Our lower bound is based on a novel property testing problem, which we analyze using Fourier analytic tools. As a byproduct of our techniques, we also achieve new lower bounds for the problem of approximating MAX-CUT value in sublinear time.

In the Prophet Secretary problem, samples from a known set of probability distributions arrive one by one in a uniformly random order, and an algorithm must irrevocably pick one of the samples as soon as it arrives. The goal is to maximize the expected value of the sample picked relative to the expected maximum of the distributions. This is one of the most simple and fundamental problems in online decision making that models the process selling one item to a sequence of costumers. For a closely related problem called the Prophet Inequality where the order of the random variables is adversarial, it is known that one can achieve in expectation 1/2 of the expected maximum, and no better ratio is possible. For the Prophet Secretary problem, that is, when the variables arrive in a random order, Esfandiari et al. (2015) showed that one can actually get 1-1/e of the maximum. The 1-1/e bound was recently extended to more general settings by Ehsani et al. (2018). Given these results, one might be tempted to believe that 1-1/e is the correct bound. We show that this is not the case by providing an algorithm for the Prophet Secretary problem that beats the 1-1/e bound and achieves 1-1/e+1/400 times the expected maximum. We also prove a hardness result on the performance of algorithms under a natural restriction which we call deterministic distribution-insensitivity.

In the min-cost bipartite perfect matching with delays (MBPMD) problem, requests arrive online at points of a finite metric space. Each request is either positive or negative and has to be matched to a request of opposite polarity. As opposed to traditional online matching problems, the algorithm does not have to serve requests as they arrive, and may choose to match them later at a cost. Our objective is to minimize the sum of the distances between matched pairs of requests (the connection cost) and the sum of the waiting times of the requests (the delay cost). This objective exhibits a natural tradeoff between minimizing the distances and the cost of waiting for better matches. This tradeoff appears in many real-life scenarios, notably, ride-sharing platforms. MBPMD is related to its non-bipartite variant, min-cost perfect matching with delays (MPMD), in which each request can be matched to any other request. MPMD was introduced by Emek et al. (STOC'16), who showed an O(log^2(n)+log(Delta))-competitive randomized algorithm on n-point metric spaces with aspect ratio Delta. Our contribution is threefold. First, we present a new lower bound construction for MPMD and MBPMD. We get a lower bound of Omega(sqrt(log(n)/log(log(n)))) on the competitive ratio of any randomized algorithm for MBPMD. For MPMD, we improve the lower bound from Omega(sqrt(log(n))) (shown by Azar et al., SODA'17) to Omega(log(n)/log(log(n))), thus, almost matching their upper bound of O(log(n)). Second, we adapt the algorithm of Emek et al. to the bipartite case, and provide a simplified analysis that improves the competitive ratio to O(log(n)). The key ingredient of the algorithm is an O(h)-competitive randomized algorithm for MBPMD on weighted trees of height h. Third, we provide an O(h)-competitive deterministic algorithm for MBPMD on weighted trees of height h. This algorithm is obtained by adapting the algorithm for MPMD by Azar et al. to the apparently more complicated bipartite setting.

We consider the problem of online Min-cost Perfect Matching with Delays (MPMD) recently introduced by Emek et al, (STOC 2016). This problem is defined on an underlying n-point metric space. An adversary presents real-time requests online at points of the metric space, and the algorithm is required to match them, possibly after keeping them waiting for some time. The cost incurred is the sum of the distances between matched pairs of requests (the connection cost), and the sum of the waiting times of the requests (the delay cost). We prove the first logarithmic upper bound and the first polylogarithmic lower bound on the randomized competitive ratio of this problem. We present an algorithm with a competitive ratio of O(log n), which improves the upper bound of O log2 n + logΔ) of Emek et al, by removing the dependence on Δ, the aspect ratio of the metric space (which can be unbounded as a function of n). The core of our algorithm is a deterministic algorithm for MPMD on metrics induced by edge-weighted trees of height h, whose cost is guaranteed to be at most O(1) times the connection cost plus O(h) times the delay cost of every feasible solution. The reduction from MPMD on arbitrary metrics to MPMD on trees is achieved using the result on embedding n-point metric spaces into distributions over weighted hierarchically separated trees of height O(log n), with distortion O(log n). We also prove a lower bound of on the competitive ratio of any randomized algorithm. This is the first lower bound which increases with n, and is attained on the metric of n equally spaced points on a line.

We present a randomized approximation algorithm for computing traveling salesperson tours in undirected regular graphs. Given an $n$-vertex, $k$-regular graph, the algorithm computes a tour of length at most $\left(1+\frac{7}{\ln k-O(1)}\right)n$, with high probability, in $O(nk \log k)$ time. This improves upon a recent result by Vishnoi (\cite{Vishnoi12}, FOCS 2012) for the same problem, in terms of both approximation factor, and running time. The key ingredient of our algorithm is a technique that uses edge-coloring algorithms to sample a cycle cover with $O(n/\log k)$ cycles with high probability, in near linear time. Additionally, we also give a deterministic $\frac{3}{2}+O\left(\frac{1}{\sqrt{k}}\right)$ factor approximation algorithm running in time $O(nk)$.

The weighted k-server problem is a generalization of the k-server problem in which the cost of moving a server of weight β_i through a distance d is β_i· d. The weighted server problem on uniform spaces models caching where caches have different write costs. We prove tight bounds on the performance of randomized memory less algorithms for this problem on uniform metric spaces. We prove that there is an α_k competitive memory less algorithm for this problem, where α_k=α_k-12+3α_k-1+1; α_1=1. On the other hand, we also prove a lower bound result, which is a strong evidence to our conjecture, that no randomized memory less algorithm can have competitive ratio better than α_k. To prove the upper bound of α_k, we develop a framework to bound from above the competitive ratio of any randomized memory less algorithm for this problem. The key technical contribution is a method for working with potential functions defined implicitly as the solution of a linear system. The result is robust in the sense that a small change in the probabilities used by the algorithm results in a small change in the upper bound on the competitive ratio. The above result has two important implications. Firstly this yields an α_k-competitive memory less algorithm for the weighted k-server problem on uniform spaces. This is the first competitive algorithm for k>2 which is memory less. For k=2, our algorithm agrees with the one given by Chrobak and Sgall. Secondly, this helps us prove that the Harmonic algorithm, which chooses probabilities in inverse proportion to weights, has a competitive ratio of kα_k. The only known competitive algorithm for every k before this work is a carefully crafted deterministic algorithm due to Fiat and Ricklin. Their algorithm uses memory crucially and their bound on competitive ratio more than 24k. Our algorithm is not only memory less, but also has a considerably improved competitive ratio of α_k