1,720,988 research outputs found
Faster algorithms for edge connectivity via random 2-out contractions
No full textWe provide a simple new randomized contraction approach to the global minimum cut problem for simple undirected graphs. The contractions exploit 2-out edge sampling from each vertex rather than the standard uniform edge sampling. We demonstrate the power of our new approach by obtaining better algorithms for sequential, distributed, and parallel models of computation. Our end results include the following randomized algorithms for computing edge connectivity, with high probability1: • Two sequential algorithms with complexities O(m log n) and O(m + n log3 n). These improve on a long line of developments including a celebrated O(m log3 n) algorithm of Karger [STOC'96] and the state of the art O(m log2 n(log log n)2) algorithm of Henzinger et al. [SODA'17]. Moreover, our O(m + n log3 n) algorithm is optimal when m = Ω(n log3 n). • An Õ(n0.8D0.2 + n0.9) round distributed algorithm, where D denotes the graph diameter. This improves substantially on a recent breakthrough of Daga et al.[STOC'19], which achieved a round complexity of Õ(n1−1/353D1/353 + n1−1/706), hence providing the first sublinear distributed algorithm for exactly computing the edge connectivity. • The first O(1) round algorithm for the massively parallel computation setting with linear memory per machine.</p
A Little Charity Guarantees Almost Envy-Freeness.
Get PDFFair division of indivisible goods is a very well-studied problem. The goal of this problem is to distribute goods to agents in a "fair" manner, where every agent has a valuation for each subset of goods. We assume general valuations. Envy-freeness is the most extensively studied notion of fairness. However, envy-free allocations do not always exist when goods are indivisible. The notion of fairness we consider here is "envy-freeness up to any good" (EFX) where no agent envies another agent after the removal of any single good from the other agent's bundle. It is not known if such an allocation always exists even when . We show there is always a partition of the set of goods into subsets where for , is the bundle allocated to agent and the set is unallocated (or donated to charity) such that we have 1) envy-freeness up to any good, 2) no agent values higher than her own bundle, and 3) fewer than goods go to charity, i.e., (typically ). Our proof is constructive. When agents have additive valuations and is large (i.e., when is close to ), our allocation also has a good maximin share (MMS) guarantee. Moreover, a minor variant of our algorithm also shows the existence of an allocation which is groupwise maximin share (GMMS): this is a notion of fairness stronger than MMS. This improves upon the current best bound of known for an approximate GMMS allocation
Deterministic algorithms for decremental approximate shortest paths:Faster and Simpler
No full textIn the decremental (1 + ∈)-Approximate Single-Source ShortEst Path (Sssp) Problem, We Are Given a Graph G = (V, E) With n = |V |, m = |E|, Undergoing Edge Deletions, and a Distinguished Source s ∈ V , and We Are Asked to Process Edge Deletions Efficiently and Answer Queries for Distance EsTimates Dist gG(s, v) for Each v ∈ V , At Any Stage, Such That Distg(s, v) ≤ Dist gG(s, v) ≤ (1 + ∈)Distg(s, v). In The DecreMental (1 + ∈)-Approximate All-Pairs Shortest Path (Apsp) Problem, We Are Asked to Answer Queries for Distance EstiMates Dist gG(u, v) for Every u, v ∈ V . In This Article, We Consider The Problems for Undirected, Unweighted Graphs. We Present a New Deterministic Algorithm for The DecreMental (1 + ∈)-Approximate Sssp Problem That Takes Total Update Time O(Mn0.5+o(1)). Our Algorithm Improves On The Currently Best Algorithm for Dense Graphs By Chechik and Bernstein [Stoc 2016] With Total Update Time Õ(n2) and The Best Existing Algorithm for Sparse Graphs With Running Time Õ(n1.25 √m) [Soda 2017] Whenever m = O(n1.5−o(1)). In Order to Obtain Our New Algorithm, We Develop SevEral New Techniques Including Improved Decremental Cover Data Structures for Graphs, a More Efficient Notion of The Heavy/Light Decomposition Framework Introduced By Chechik and Bernstein and The First Clustering Technique to Maintain a Dynamic Sparse Emulator In The Deterministic SetTing. As a By-Product, We Also Obtain a New Simple DeterMinistic Algorithm for The Decremental (1 + ∈)-Approximate Apsp Problem With Near-Optimal Total Running Time Õ(Mn/∈) matching the time complexity of the sophisticated but rather involved algorithm by Henzinger, Forster and Nanongkai [FOCS 2013].</p
A Lower Bound for Jumbled Indexing
No full textIn this paper we study lower bounds for a variant of jumbled-indexing problem: given an input string S on an alphabet Σ = {σ1, . . ., σλ}, store it in a data structure such that given frequencies f1, · · ·, fλ, one can find all the substrings S0 of S where the frequency of the character σi is fi, for 1 ≤ i ≤ λ. This is a very interesting and challenging text indexing problem and it has received significant attention lately, both in the string-indexing community as well as in the theory community. It is known that when λ = 2, one can use a linear-size data structure to decide whether there exists a substring that matches the query in constant time [10]. It is also known [1] that for constant λ ≥ 3, then there exists a constant αλ such that it is not possible to achieve both O(n2−αλ) preprocessing time and O(n1−αλ) query time. We study a variant of the problem where the goal is to report all the substrings of S that match a given jumbled-indexing query. Assuming the data structure operates in the pointer machine model, we prove unconditional space lower bounds that also apply to binary alphabets: we show that if the data structure has the query time of O(n0.5−o(1) + k), where k is the output size of the query, then it must consume Ω(n2−o(1)) space. The o(1) term in our lower bound is at most log(10)1n, where log(·) notation denotes the iterative log function (i.e., log(10) n = log log log log log log log log log log n). This result has a number of interesting consequences. First, it shows that reporting all the matches is significantly harder than deciding whether a match exists, at least for the binary alphabet. This was surprising for us since we believed that in order for jumbled-indexing to be difficult, the alphabet size must be at least 3. Second, from a technical point of view, we make connections between this problem and the area of additive combinatorics as well as random walks. Previously, Chan and Lewenstein [6] had shown the connections between this problem and the area of additive combinatorics from an upper bound point of view, however, we use fundamental theorems from additive combinatorics but these tools are quite different from the theorems used in [6]. In our opinion, the fact that additive combinatorics appears in our lower bound approach as well as in the upper bound approach of Chan and Lewenstein [6] is noteworthy and demands further investigation. We believe our results open up a few new venues for research. For example, we believe it is interesting to study whether it is possible to build a data structure that uses O(n) space s.t., it can report all the matches to a jumble-indexing query in O(n2/3 + k) time; this is even interesting for a binary alphabet.<br/
The Complexity of Contracts
No full textWe initiate the study of computing (near-)optimal contracts in succinctly representable principal-agent settings. Here optimality means maximizing the principal's expected payoff over all incentive-compatible contracts-known in economics as “second-best” solutions. We also study a natural relaxation to approximately incentive-compatible contracts. We focus on principal-agent settings with succinctly described (and exponentially large) outcome spaces. We show that the computational complexity of computing a near-optimal contract depends fundamentally on the number of agent actions. For settings with a constant number of actions, we present a fully polynomial-time approximation scheme (FPTAS) for the separation oracle of the dual of the problem of minimizing the principal's payment to the agent, and use this subroutine to efficiently compute a δ-incentivecompatible (δ-IC) contract whose expected payoff matches or surpasses that of the optimal IC contract. With an arbitrary number of actions, we prove that the problem is hard to approximate within any constant c. This inapproximability result holds even for δ-IC contracts where δ is a sufficiently rapidly-decaying function of c. On the positive side, we show that simple linear δ-IC contracts with constant δ are sufficient to achieve a constant-factor approximation of the “first-best” (full-welfare-extracting) solution, and that such a contract can be computed in polynomial time
Worst-Case Polylog Incremental SPQR-trees:Embeddings, Planarity, and Triconnectivity
No full textWe show that every labelled planar graph G can be assigned a canonical embedding φ(G), such that for any planar G’ that differs from G by the insertion or deletion of one edge, the number of local changes to the combinatorial embedding needed to get from φ(G) to φ(G’) is (log n).In contrast, there exist embedded graphs where Ω(n) changes are necessary to accommodate one inserted edge. We provide a matching lower bound of Ω(log n) local changes, and although our upper bound is worst-case, our lower bound hold in the amortized case as well.Our proof is based on BC trees and SPQR trees, and we develop pre-split variants of these for general graphs, based on a novel biased heavy-path decomposition, where the structural changes corresponding to edge insertions and deletions in the underlying graph consist of at most (log n) basic operations of a particularly simple form.As a secondary result, we show how to maintain the pre-split trees under edge insertions in the underlying graph deterministically in worst case (log3 n) time. Using this, we obtain deterministic data structures for incremental planarity testing, incremental planar embedding, and incremental triconnectivity, that each have worst case (log3 n) update and query time, answering an open question by La Poutré and Westbrook from 1998.<br/
Oblivious Sketching of High-Degree Polynomial Kernels
Get PDFKernel methods are fundamental tools in machine learning that allow detection of non-linear dependencies between data without explicitly constructing feature vectors in high dimensional spaces. A major disadvantage of kernel methods is their poor scalability: primitives such as kernel PCA or kernel ridge regression generally take prohibitively large quadratic space and (at least) quadratic time, as kernel matrices are usually dense. Some methods for speeding up kernel linear algebra are known, but they all invariably take time exponential in either the dimension of the input point set (e.g., fast multipole methods suffer from the curse of dimensionality) or in the degree of the kernel function. Oblivious sketching has emerged as a powerful approach to speeding up numerical linear algebra over the past decade, but our understanding of oblivious sketching solutions for kernel matrices has remained quite limited, suffering from the aforementioned exponential dependence on input parameters. Our main contribution is a general method for applying sketching solutions developed in numerical linear algebra over the past decade to a tensoring of data points without forming the tensoring explicitly. This leads to the first oblivious sketch for the polynomial kernel with a target dimension that is only polynomially dependent on the degree of the kernel function, as well as the first oblivious sketch for the Gaussian kernel on bounded datasets that does not suffer from an exponential dependence on the dimensionality of input data points.THL
Decremental SSSP in weighted digraphs:Faster and against an adaptive adversary
No full textGiven a dynamic digraph G = (V, E) undergoing edge deletions and given s ∈ V and constant ǫ with 0 < ǫ ≤ 1, we consider the problem of maintaining (1+ǫ)-approximate shortest path distances from s to all vertices in G over the sequence of deletions. Even and Shiloach (J. ACM'81) give a deterministic data structure for the exact version of the problem in unweighted graphs with total update time O(mn). Henzinger et al. (STOC'14, ICALP'15) give a Monte Carlo data structure for the approximate version with an improved total update time bound of O(mn0.9+o(1) log W) with better bounds for sufficiently dense and sufficiently sparse graphs; here W is the ratio between the largest and smallest edge weight. A drawback of their data structure and in fact of all previous randomized data structures is that they only work against an oblivious adversary, meaning that the sequence of deletions needs to be fixed in advance. This severely limits its application as a black box inside algorithms. We present the following (1 + ǫ)-approximate data structures: 1. the first data structure is Las Vegas and works against an adaptive adversary; it has total expected update time Õ(m2/3n4/3)1 for unweighted graphs and Õ(m3/4n5/4 log W) for weighted graphs, 2. the second data structure is Las Vegas and assumes an oblivious adversary; it has total expected update time Õ(√mn3/2) for unweighted graphs and Õ(m2/3n4/3 log W) for weighted graphs, 3. the third data structure is Monte Carlo and is correct w.h.p. against an oblivious adversary; it has total expected update time Õ((mn)7/8 log W) = Õ(mn3/4 log W). Each of our data structures can report the length of a (1+ǫ)-approximate shortest path from s to any query vertex in constant time at any point during the sequence of updates; if the adversary is oblivious, a query can be extended to also report such a path in time proportional to its length. Our update times are faster than those of Henzinger et al. for all graph densities. For instance, when m = Θ(n2), our second result improves their bound from O(n2+3/4+o(1) log W) to Õ(n2+1/2) in the unweighted setting and to Õ(n2+2/3 log W) in the weighted setting. When m = Θ(n), our third result gives an improvement from O(n1+5/6+o(1) log W) to Õ(n1+3/4 log W). Furthermore, our first data structure is the first to improve on the O(mn) bound of Even and Shiloach for all but the sparsest graphs while still working against an adaptive adversary and works even in weighted graphs; this answers an open problem by Henzinger et al.</p
Approximately Counting and Sampling Small Witnesses Using a Colourful Decision Oracle
Get PDFIn this paper, we prove "black box" results for turning algorithms which decide whether or not a witness exists into algorithms to approximately count the number of witnesses, or to sample from the set of witnesses approximately uniformly, with essentially the same running time. We do so by extending the framework of Dell and Lapinskas (STOC 2018), which covers decision problems that can be expressed as edge detection in bipartite graphs given limited oracle access; our framework covers problems which can be expressed as edge detection in arbitrary k-hypergraphs given limited oracle access. (Simulating this oracle generally corresponds to invoking a decision algorithm.) This includes many key problems in both the fine-grained setting (such as k-SUM, k-OV and weighted k-Clique) and the parameterised setting (such as induced subgraphs of size k or weight-k solutions to CSPs). From an algorithmic standpoint, our results will make the development of new approximate counting algorithms substantially easier; indeed, it already yields a new state-of-the-art algorithm for approximately counting graph motifs, improving on Jerrum and Meeks (JCSS 2015) unless the input graph is very dense and the desired motif very small. Our k-hypergraph reduction framework generalises and strengthens results in the graph oracle literature due to Beame et al. (ITCS 2018) and Bhattacharya et al. (CoRR abs/1808.00691)
Sandwiching random regular graphs between binomial random graphs
No full textKim and Vu made the following conjecture (Advances in Mathematics, 2004): if d ≫ log n, then the random dregular graph G(n, d) can asymptotically almost surely be “sandwiched” between G(n, p1) and G(n, p2) where p1 and p2 are both (1 + o(1))d/n. They proved this conjecture for log n ≪ d 6 n1/3−o(1), with a defect in the sandwiching: G(n, d) contains G(n, p1) perfectly, but is not completely contained in G(n, p2). Recently, the embedding G(n, p1) ⊆ G(n, d) was improved by Dudek, Frieze, Ruci´ nski and Šileikis to d = o(n). In this paper, we prove Kim-Vu's sandwich conjecture, with perfect containment on both sides, for all d ≫ n/√log n. For d = O(n/√log n), we prove a weaker version of the sandwich conjecture with p2 approximately equal to (d/n) log n, without any defect. In addition to sandwiching regular graphs, our results cover graphs whose degrees are asymptotically equal. The proofs rely on estimates for the probability that a random factor of a pseudorandom graph contains a given edge, which is of independent interest. As applications, we obtain new results on the properties of random graphs with given near-regular degree sequences, including Hamiltonicity and universality in subgraph containment. We also determine several graph parameters in these random graphs, such as the chromatic number, small subgraph counts, the diameter, and the independence number. We are also able to characterise many phase transitions in edge percolation on these random graphs, such as the threshold for the appearance of a giant component.</p
- …
