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.

Center-based clustering techniques are fundamental to many real-world applications such as data summarization and social network analysis. In this work, we study the problem of fairness aware k-center clustering over large datasets. We are given an input dataset comprising a set of n points, where each point belongs to a specific demographic group characterized by a protected attribute, such as race or gender. The goal is to identify k clusters such that all clusters have considerable representation from all groups and the maximum radius of these clusters is minimized.

Graphs and games on graphs are fundamental models for the analysis of reactive systems, in particular, for model-checking and the synthesis of reactive systems. The class of ω-regular languages provides a robust specification formalism for the desired properties of reactive systems. In the classical infinitary formulation of the liveness part of an ω-regular specification, a "good" event must happen eventually without any bound between the good events. A stronger notion of liveness is bounded liveness, which requires that good events happen within d transitions. Given a graph or a game graph with n vertices, m edges, and a bounded liveness objective, the previous best-known algorithmic bounds are as follows: (i) O(dm) for graphs, which in the worst-case is O(n³); and (ii) O(n² d²) for games on graphs. Our main contributions improve these long-standing algorithmic bounds. For graphs we present: (i) a randomized algorithm with one-sided error with running time O(n^{2.5} log n) for the bounded liveness objectives; and (ii) a deterministic linear-time algorithm for the complement of bounded liveness objectives. For games on graphs, we present an O(n² d) time algorithm for the bounded liveness objectives.

With input sizes becoming massive, coresets - small yet representative summary of the input - are relevant more than ever. A weighted set C_w that is a subset of the input is an ε-coreset if the cost of any feasible solution S with respect to C_w is within [1±ε] of the cost of S with respect to the original input. We give a very general technique to compute coresets in the fully-dynamic setting where input points can be added or deleted. Given a static (i.e., not dynamic) ε-coreset-construction algorithm that runs in time t(n, ε, λ) and computes a coreset of size s(n, ε, λ), where n is the number of input points and 1-λ is the success probability, we give a fully-dynamic algorithm that computes an ε-coreset with worst-case update time O((log n) ⋅ t(s(n, ε/log n, λ/n), ε/log n, λ/n)) (this bound is stated informally), where the success probability is 1-λ. Our technique is a fully-dynamic analog of the merge-and-reduce technique, which is due to Har-Peled and Mazumdar [Har-Peled and Mazumdar, 2004] and is based on a technique of Bentley and Saxe [Jon Louis Bentley and James B. Saxe, 1980], that applies to the insertion-only setting where points can only be added. Although, our space usage is O(n), our technique works in the presence of an adaptive adversary, and we show that Ω(n) space is required when adversary is adaptive. As a concrete implication of our technique, using the result of Braverman et al. [{Braverman} et al., 2016], we get fully-dynamic ε-coreset-construction algorithms for k-median and k-means with worst-case update time O(ε^{-2} k² log⁵ n log³ k) and coreset size O(ε^{-2} k log n log² k) ignoring log log n and log(1/ε) factors and assuming that ε = Ω(1/poly(n)) and λ = Ω(1/poly(n)) (which are very weak assumptions made only to make these bounds easy to parse). This results in the first fully-dynamic constant-approximation algorithms for k-median and k-means with update times O(poly(k, log n, ε^{-1})). Specifically, the dependence on k is only quadratic, and the bounds are worst-case. The best previous bound for both problems was amortized O(nlog n) by Cohen-Addad et al. [Cohen-Addad et al., 2019] via randomized O(1)-coresets in O(n) space. We also show that under the OMv conjecture [Monika Henzinger et al., 2015], a fully-dynamic (4 - δ)-approximation algorithm for k-means must either have an amortized update time of Ω(k^{1-γ}) or amortized query time of Ω(k^{2 - γ}), where γ > 0 is a constant.

In this paper, we study streaming and online algorithms in the context of randomness in the input. For several problems, a random order of the input sequence---as opposed to the worst-case order---appears to be a necessary evil in order to prove satisfying guarantees. However, algorithmic techniques that work under this assumption tend to be vulnerable to even small changes in the distribution. For this reason, we propose a new \emph{adversarial injections} model, in which the input is ordered randomly, but an adversary may inject misleading elements at arbitrary positions. We believe that studying algorithms under this much weaker assumption can lead to new insights and, in particular, more robust algorithms. We investigate two classical combinatorial-optimization problems in this model: Maximum matching and cardinality constrained monotone submodular function maximization. Our main technical contribution is a novel streaming algorithm for the latter that computes a $0.55$-approximation. While the algorithm itself is clean and simple, an involved analysis shows that it emulates a subdivision of the input stream which can be used to greatly limit the power of the adversary.

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.

In the matroid center problem, which generalizes the $k$-center problem, we need to pick a set of centers that is an independent set of a matroid with rank $r$. We study this problem in streaming, where elements of the ground set arrive in the stream. We first show that any randomized one-pass streaming algorithm that computes a better than $Δ$-approximation for partition-matroid center must use $Ω(r^2)$ bits of space, where $Δ$ is the aspect ratio of the metric and can be arbitrarily large. This shows a quadratic separation between matroid center and $k$-center, for which the Doubling algorithm gives an $8$-approximation using $O(k)$-space and one pass. To complement this, we give a one-pass algorithm for matroid center that stores at most $O(r^2\log(1/\varepsilon)/\varepsilon)$ points (viz., stream summary) among which a $(7+\varepsilon)$-approximate solution exists, which can be found by brute force, or a $(17+\varepsilon)$-approximation can be found with an efficient algorithm. If we are allowed a second pass, we can compute a $(3+\varepsilon)$-approximation efficiently; this also achieves almost the known-best approximation ratio (of $3+\varepsilon$) with total running time of $O((nr + r^{3.5})\log(1/\varepsilon)/\varepsilon + r^2(\log Δ)/\varepsilon)$, where $n$ is the number of input points. We also consider the problem of matroid center with $z$ outliers and give a one-pass algorithm that outputs a set of $O((r^2+rz)\log(1/\varepsilon)/\varepsilon)$ points that contains a $(15+\varepsilon)$-approximate solution. Our techniques extend to knapsack center and knapsack center with outliers in a straightforward way, and we get algorithms that use space linear in the size of a largest feasible set (as opposed to quadratic space for matroid center).

We design a generic method to reduce the task of finding weighted matchings to that of finding short augmenting paths in unweighted graphs. This method enables us to provide efficient implementations for approximating weighted matchings in the massively parallel computation (MPC) model and in the streaming model.

We consider the maximum bipartite matching problem in stochastic settings, namely the query-commit and price-of-information models. In the query-commit model, an edge e independently exists with probability pe. We can query whether an edge exists or not, but if it does exist, then we have to take it into our solution. In the unweighted case, one can query edges in the order given by the classical online algorithm of Karp, Vazirani, and Vazirani [20] to get a (1 – 1/e)-approximation. In contrast, the previously best known algorithm in the weighted case is the (1/2)-approximation achieved by the greedy algorithm that sorts the edges according to their weights and queries in that order. Improving upon the basic greedy, we give a (1 – 1/e)-approximation algorithm in the weighted query-commit model. We use a linear program (LP) to upper bound the optimum achieved by any strategy. The proposed LP admits several structural properties that play a crucial role in the design and analysis of our algorithm. We also extend these techniques to get a (1 – 1/e)-approximation algorithm for maximum bipartite matching in the price-of-information model introduced by Singla [25], who also used the basic greedy algorithm to give a (1/2)-approximation.

We consider the problem of approximating a maximum weighted matching, when the edges of an underlying weighted graph $G(V,E)$ are revealed in a streaming fashion. We analyze a variant of the previously best-known $(4+ε)$-approximation algorithm due to Crouch and Stubbs (APPROX, 2014), and prove their conjecture that it achieves a tight approximation factor of $3.5+ε$. The algorithm splits the stream into substreams on which it runs a greedy maximum matching algorithm. At the end of the stream, the selected edges are given as input to an optimal maximum weighted matching algorithm. To analyze the approximation guarantee, we develop a novel charging argument in which we decompose the edges of a maximum weighted matching of $G$ into a few natural classes, and then charge them separately to the edges of the matching output by our algorithm.

We develop a paradigm for studying multi-player deterministic communication, based on a novel combinatorial concept that we call a strong fooling set. Our paradigm leads to optimal lower bounds on the per-player communication required for solving multi-player EQUALITY problems in a private-message setting. This in turn gives a very strong - O(1) versus Ω(n) - separation between private-message and one-way blackboard communication complexities. Applying our communication complexity results, we show that for deterministic data streaming algorithms, even loose estimations of some basic statistics of an input stream require large amounts of space. For instance, approximating the frequency moment Fkwithin a factor α requires Ω(n/α1/(1-k)) space for k > 1 and roughly Ω(n/αk/(k-1)) space for k > 1. In particular, approximation within any constant factor α, however large, requires linear space, with the trivial exception of k = 1. This is in sharp contrast to the situation for randomized streaming algorithms, which can approximate Fkto within (1±ε) factors using Õ(1) space for k ≤ 2 and o(n) space for all finite k and all constant ε > 0. Previous linear-space lower bounds for deterministic estimation were limited to small factors α, such as α0or F2. We also provide certain space/approximation tradeoffs in a deterministic setting for the problems of estimating the empirical entropy of a stream as well as the size of the maximum matching and the edge connectivity of a streamed graph.