Computing the connected components of a graph is a fundamental problem in algorithmic graph theory. A major question in this area is whether we can compute connected components in o(log n) parallel time. Recent works showed an affirmative answer in the Massively Parallel Computation (MPC) model for a wide class of graphs. Specifically, Behnezhad et al. (FOCS'19) showed that connected components can be computed in O(log d + log log n) rounds in the MPC model. More recently, Liu et al. (SPAA'20) showed that the same result can be achieved in the standard PRAM model but their result incurs Θ((m+n) ⋅ (log d + log log n)) work which is sub-optimal.

In the stochastic weighted matching problem, the goal is to find a large-weight matching of a graph when we are uncertain about the existence of its edges. In particular, each edge e has a known weight we but is realized independently with some probability pe. The algorithm may query an edge to see whether it is realized. We consider the well-studied query commit version of the problem, in which any queried edge that happens to be realized must be included in the solution. Gamlath, Kale, and Svensson [SODA'19] showed that when the input graph is bipartite, the problem admits a (1 — 1/e)-approximation. In this paper, we give an algorithm that obtains a (1 — 1/e + δ)-approximation for an absolute constant δ > 0.0014, therefore breaking this prevalent bound.

In this paper, we generalize the recently studied stochastic matching problem to more accurately model a significant medical process, kidney exchange, and several other applications. Up until now the stochastic matching problem that has been studied was as follows: given a graph G= (V,E), each edge is included in the realized sub-graph of G independently with probability pe, and the goal is to find a degree-bounded sub-graph Q of G that has an expected maximum matching that approximates the expected maximum matching of G. This model does not account for possibilities of vertex dropouts, which can be found in several applications, e.g. in kidney exchange when donors or patients opt out of the exchange process as well as in online freelancing and online dating when online profiles are found to be faked. Thus, we will study a more generalized model of stochastic matching in which vertices and edges are both realized independently with some probabilities pv, pe, respectively, which more accurately fits important applications than the previously studied model. We will discuss the first algorithms and analysis for this generalization of the stochastic matching model and prove that they achieve good approximation ratios. In particular, we show that the approximation factor of a natural algorithm for this problem is at least 0.6568 in unweighted graphs, and 1/2+ε in weighted graphs for some constant ε >0. We further improve our result for unweighted graphs to 2/3 using edge degree constrained sub-graphs (EDCS).

Given a graph, the densest subgraph problem asks for a set of vertices such that the average degree among these vertices is maximized. Densest subgraph has numerous applications in learning, e.g., community detection in social networks, link spam detection, correlation mining, bioinformatics, and so on. Although there are efficient algorithms that output either exact or approximate solutions to the densest subgraph problem, existing algorithms may violate the privacy of the individuals in the network, e.g., leaking the existence/non-existence of edges. In this paper, we study the densest subgraph problem in the framework of the differential privacy, and we derive the upper and lower bounds for this problem. We show that there exists a linear-time $\epsilon$-differentially private algorithm that finds a 2-approximation of the densest subgraph with an extra poly-logarithmic additive error. Our algorithm not only reports the approximate density of the densest subgraph, but also reports the vertices that form the dense subgraph. Our upper bound almost matches the famous 2-approximation by Charikar both in performance and in approximation ratio, but we additionally achieve differential privacy. In comparison with Charikar’s algorithm, our algorithm has an extra poly logarithmic additive error. We partly justify the additive error with a new lower bound, showing that for any differentially private algorithm that provides a constant-factor approximation, a sub-logarithmic additive error is inherent. We also practically study our differentially private algorithm on real-world graphs, and we show that in practice the algorithm finds a solution which is very close to the optimal.

We study the classic online bipartite matching problem with a twist: offline nodes are reusable any number of times. Every offline node i becomes available d steps after it was assigned to. Nothing better than a 0.5-approximation, obtained by the trivial deterministic greedy algorithm, was known for this problem. We give the first approximation factor beating 0.5, namely a 0.505 approximation, by suitably adapting and interpreting the powerful technique of Online Correlated Selection.

Envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX) are two well-known extensions of envy-freeness for the case of indivisible items. It is shown that EF1 can always be guaranteed for agents with subadditive valuations. In sharp contrast, it is unknown whether or not an EFX allocation always exists, even for four agents and additive valuations. In addition, the best approximation guarantee for EFX is (φ − 1) ≃ 0.61 by Amanitidis et al.. In order to find a middle ground to bridge this gap, in this paper we suggest another fairness criterion, namely envy-freeness up to a random good or EFR, which is weaker than EFX, yet stronger than EF1. For this notion, we provide a polynomial-time 0.73-approximation allocation algorithm. For our algorithm we introduce Nash Social Welfare Matching which makes a connection between Nash Social Welfare and envy freeness.

The edit distance (ED) and longest common subsequence (LCS) are two fundamental problems which quantify how similar two strings are to one another. In this paper, we first consider these problems in the asymmetric streaming model introduced by Andoni, Krauthgamer and Onak [Andoni et al., 2010] (FOCS'10) and Saks and Seshadhri [Saks and Seshadhri, 2013] (SODA'13). In this model we have random access to one string and streaming access the other one. Our main contribution is a constant factor approximation algorithm for ED with memory Õ(n^δ) for any constant δ > 0. In addition to this, we present an upper bound of Õ _ε(√n) on the memory needed to approximate ED or LCS within a factor 1±ε. All our algorithms are deterministic and run in polynomial time in a single pass. We further study small-space approximation algorithms for ED, LCS, and longest increasing sequence (LIS) in the non-streaming setting. Here, we design algorithms that achieve 1 ± ε approximation for all three problems, where ε > 0 can be any constant and even slightly sub-constant. Our algorithms only use poly-logarithmic space while maintaining a polynomial running time. This significantly improves previous results in terms of space complexity, where all known results need to use space at least Ω(√n). Our algorithms make novel use of triangle inequality and carefully designed recursions to save space, which can be of independent interest.

In this paper, we study the problem of finding a maximum matching in the semi-streaming model when edges arrive in a random order. In the semi-streaming model, an algorithm receives a stream of edges and it is allowed to have a memory of Õ(n)1 where n is the number of vertices in the graph. A recent inspiring work by Assadi et al. [1] shows that there exists a streaming algorithm with the approximation ratio of ⅔ that uses Õ(n1.5) memory. However, the memory of their algorithm is much larger than the memory constraint of the semi-streaming algorithms. In this work, we further investigate this problem in the semi-streaming model, and we present simple and clean algorithms for approximating maximum matching in the semi-streaming model. Our main results are as follows. We show that there exists a single-pass deterministic semi-streaming algorithm that finds a approximation of the maximum matching in bipartite graphs using Õ(n) memory. This result significantly outperforms the state-of-the-art result of Konrad [12] that finds a 0.539 approximation of the maximum matching using Õ(n) memory. By giving a black-box reduction from finding a matching in general graphs to finding a matching in bipartite graphs, we show there exists a single-pass deterministic semi-streaming algorithm that finds a (≈ 0.545) approximation of the maximum matching in general graphs, improving upon the state-of-art result 0.506 approximation by Gamlath et al. [8].

The k-cut problem asks, given a connected graph G and a positive integer k, to find a minimum-weight set of edges whose removal splits G into k connected components. We give the first polynomial-time algorithm with approximation factor 2 – ∊ (with constant ∊ > 0) for the k-cut problem in planar and minor-free graphs. Applying more complex techniques, we further improve our method and give a polynomial-time approximation scheme for the k-cut problem in both planar and minor-free graphs. Despite persistent effort, to the best of our knowledge, this is the first improvement for the k-cut problem over standard approximation factor of 2 in any major class of graphs.

We consider the following stochastic matching problem on both weighted and unweighted graphs: A graph G(V, E) along with a parameter p ∊ (0, 1) is given in the input. Each edge of G is realized independently with probability p. The goal is to select a degree bounded (dependent only on p) subgraph H of G such that the expected maximum realized matching of H is close to that of G. This model of stochastic matching has attracted significant attention over the recent years due to its various applications in kidney exchange, online labor markets, and other matching markets. The most fundamental open question is the best approximation factor achievable for such algorithms that, in the literature, are referred to as non-adaptive algorithms. Prior work has identified breaking (near) half-approximation as a barrier for both weighted and unweighted graphs. Our main results are as follows: We analyze a simple and clean algorithm and show that for unweighted graphs, it finds an (almost) (≈ 0.6568) approximation by querying Õ(1/p) edges per vertex. This improves over the state-of-the-art 0.5001 approximation of Assadi et al. [EC’17]. We show that the same algorithm achieves a 0.501 approximation for weighted graphs by querying Õ(1/p) edges per vertex. This improves both, the approximation factor and the per-vertex queries of the 0.5 – ∊ approximations of Yamaguchi and Maehara [SODA’18] and Behnezhad and Reyhani [EC’18] which respectively required up to O(W log n/∊p) and O(1/p4/∊) queries.1 Interestingly, prior results were all based on similar algorithms and differed only in the analysis. Our algorithms are fundamentally different, yet very simple and natural. For the analysis, we introduce a number of procedures that construct heavy fractional matchings. We consider the new algorithms and our analytical tools to be the main contributions of this paper.

Sorting extremely large datasets is a frequently occuring task in practice. These datasets are usually much larger than the computer’s main memory; thus external memory sorting algorithms, first introduced by Aggarwal and Vitter (1988), are often used. The complexity of comparison based external memory sorting has been understood for decades by now, however the situation remains elusive if we assume the keys to be sorted are integers. In internal memory, one can sort a set of n integer keys of Θ(lgn) bits each in O(n) time using the classic Radix Sort algorithm, however in external memory, there are no faster integer sorting algorithms known than the simple comparison based ones. Whether such algorithms exist has remained a central open problem in external memory algorithms for more than three decades.

We study fair allocation of indivisible goods to agents with unequal entitlements. Fair allocation has been the subject of many studies in both divisible and indivisible settings. Our emphasis is on the case where the goods are indivisible and agents have unequal entitlements. This problem is a generalization of the work by Procaccia and Wang (2014) wherein the agents are assumed to be symmetric with respect to their entitlements. Although Procaccia and Wang show an almost fair (constant approximation) allocation exists in their setting, our main result is in sharp contrast to their observation. We show that, in some cases with n agents, no allocation can guarantee better than 1/n approximation of a fair allocation when the entitlements are not necessarily equal. Furthermore, we devise a simple algorithm that ensures a 1/n approximation guarantee. Our second result is for a restricted version of the problem where the valuation of every agent for each good is bounded by the total value he wishes to receive in a fair allocation. Although this assumption might seem without loss of generality, we show it enables us to find a 1/2 approximation fair allocation via a greedy algorithm. Finally, we run some experiments on real-world data and show that, in practice, a fair allocation is likely to exist. We also support our experiments by showing positive results for two stochastic variants of the problem, namely stochastic agents and stochastic items.

Sorting extremely large datasets is a frequently occurring task in practice. These datasets are usually much larger than the computer's main memory; thus external memory sorting algorithms, first introduced by Aggarwal and Vitter [ Commun. ACM, 31 (1988), pp. 1116--1127], are often used. The complexity of comparison based external memory sorting has been understood for decades by now, but the situation remains elusive if we assume the keys to be sorted are integers. In internal memory, one can sort a set of $n$ integer keys of $\Theta({lg} n)$ bits each in $O(n)$ time using the classic radix sort algorithm, but in external memory, there are no faster integer sorting algorithms known than the simple comparison based ones. Whether such algorithms exist has remained a central open problem in external memory algorithms for more than three decades. In this paper, we present a tight conditional lower bound on the complexity of external memory sorting of integers. Our lower bound is based on a famous conjecture in network coding by Li and Li [ Proceedings of the 42nd Allerton Annual Conference on Communication, Control and Computing, 2004], who conjectured that network coding cannot help anything beyond the standard multicommodity flow rate in undirected graphs. The only previous work connecting the Li and Li conjecture to lower bounds for algorithms is due to Adler et al. [ Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm, 2006, pp. 241--250]. Adler et al. indeed obtain relatively simple lower bounds for oblivious algorithms (the memory access pattern is fixed and independent of the input data). Unfortunately obliviousness is a strong limitation, especially for integer sorting: we show that the Li and Li conjecture implies an $\Omega(n \log n)$ lower bound for internal memory oblivious sorting when the keys are $\Theta({lg} n)$ bits. This is in sharp contrast to the classic (nonoblivious) radix sort algorithm. Indeed going beyond obliviousness is highly nontrivial; we need to introduce several new methods and involved techniques, which are of their own interest, to obtain our tight lower bound for external memory integer sorting.

We study the proportional chore division problem where a protocol wants to divide an undesirable object, called chore, among n different players. This problem is the dual variant of the cake cutting problem in which we want to allocate a desirable object. In this paper, we show that chore division and cake cutting problems are closely related to each other and provide a tight lower bound for proportional chore division.

Chore division, introduced by Gardner in 1970s [10], is the problem of fairly dividing a chore among n different agents. In particular, in an envy-free chore division, we would like to divide a negatively valued heterogeneous object among a number of agents who have different valuations for different parts of the object, such that no agent envies another agent. It is the dual variant of the celebrated cake cutting problem, in which we would like to divide a desirable object among agents. There has been an extensive amount of study and effort to design bounded and envy-free protocols/algorithms for fair division of chores and goods, such that envy-free cake cutting became one of the most important open problems in 20-th century mathematics according to Garfunkel [11]. However, despite persistent efforts, due to delicate nature of the problem, there was no bounded protocol known for cake cutting even among four agents, until the breakthrough of Aziz and Mackenzie [2], which provided the first discrete and bounded envy-free protocol for cake cutting for four agents. Afterward, Aziz and Mackenzie [3], generalized their work and provided an envy-free cake cutting protocol for any number of agents to settle a significant and longstanding open problem. However, there is much less known for chore division. Unfortunately, there is no general method known to apply cake cutting techniques to chore division. Thus, it remained an open problem to find a discrete and bounded envy-free chore division protocol even for four agents. In this paper, we provide the first discrete and bounded envy-free protocol for chore division for an arbitrary number of agents. We produce major and powerful tools for designing protocols for the fair division of negatively valued objects. These tools are based on structural results and important observations. In general, we believe these structures and techniques may be useful not only in chore division but also in other fairness problems. Interestingly, we show that applying these techniques simplifies Core Protocol provided in Aziz and Mackenzie [3].