The Lovasz Local Lemma due to Erdos and Lovasz is a powerful tool in proving the existence of rare events. We present an extension of this lemma, which works well when the event to be shown to exist is a conjunction of individual events, each of which asserts that a random variable does not deviate much from its mean. As applications, we consider two classes of NP-hard integer programs: minimax and covering integer programs. A key technique, randomized rounding of linear relaxations, was developed by Raghavan and Thompson to derive good approximation algorithms for such problems. We use our extension of the Local Lemma to prove that randomized rounding produces, with non-zero probability, much better feasible solutions than known before, if the constraint matrices of these integer programs are column-sparse (e.g., routing using short paths, problems on hypergraphs with small dimension degree). This complements certain well-known results from discrepancy theory. We also generalize the method of pessimistic estimators due to Raghavan, to obtain constructive (algorithmic) versions of our results for covering integer programs.
Given an ILP, we can find an optimal solution @math to its LP relaxation efficiently, but need to round fractional entries in @math to integers. The idea of randomized rounding is: given a real @math , round @math to @math with probability @math , and round @math to @math with probability @math . This has the nice property that the mean outcome is @math . Starting with this idea, the analysis of @cite_22 produces an integral solution of value at most @math for MIPs (though phrased a bit differently); this is derandomized in @cite_20 . But this does not exploit the sparsity of @math ; the previously-mentioned result of @cite_5 produces an integral solution of value at most @math .
@cite_5 @cite_22 @cite_20
2064779029 2022191808 2024631575
We study approximate distributed solutions to the weighted all-pairs-shortest-paths (APSP) problem in the CONGEST model. We obtain the following results. @math A deterministic @math -approximation to APSP in @math rounds. This improves over the best previously known algorithm, by both derandomizing it and by reducing the running time by a @math factor. In many cases, routing schemes involve relabeling, i.e., assigning new names to nodes and require that these names are used in distance and routing queries. It is known that relabeling is necessary to achieve running times of @math . In the relabeling model, we obtain the following results. @math A randomized @math -approximation to APSP, for any integer @math , running in @math rounds, where @math is the hop diameter of the network. This algorithm simplifies the best previously known result and reduces its approximation ratio from @math to @math . Also, the new algorithm uses uses labels of asymptotically optimal size, namely @math bits. @math A randomized @math -approximation to APSP, for any integer @math , running in time @math and producing compact routing tables of size @math . The node lables consist of @math bits. This improves on the approximation ratio of @math for tables of that size achieved by the best previously known algorithm, which terminates faster, in @math rounds. This paper addresses the cornerstone family of in distributed computing, and investigates the curious gap between randomized and deterministic solutions under bandwidth restrictions. Our main contribution is in providing tools for derandomizing solutions to local problems, when the @math nodes can only send @math -bit messages in each round of communication. We combine bounded independence, which we show to be sufficient for some algorithms, with the method of conditional expectations and with additional machinery, to obtain the following results. Our techniques give a deterministic maximal independent set (MIS) algorithm in the CONGEST model, where the communication graph is identical to the input graph, in @math rounds, where @math is the diameter of the graph. The best known running time in terms of @math alone is @math , which is super-polylogarithmic, and requires large messages. For the CONGEST model, the only known previous solution is a coloring-based @math -round algorithm, where @math is the maximal degree in the graph. On the way to obtaining the above, we show that in the model, which allows all-to-all communication, there is a deterministic MIS algorithm that runs in @math rounds. , where @math is the maximum degree. When @math , the bound improves to @math and holds also for @math -coloring. In addition, we deterministically construct a @math -spanner with @math edges in @math rounds. For comparison, in the more stringent CONGEST model, the best deterministic algorithm for constructing a @math -spanner with @math edges runs in @math rounds. In the subgraph-freeness problem, we are given a constant-size graph @math , and wish to determine whether the network contains @math as a subgraph or not. The relaxation of the problem only requires us to distinguish graphs that are @math -free from graphs that are @math -far from @math -free, meaning an @math -fraction of their edges must be removed to obtain an @math -free graph. Recently, Censor-Hillel et. al. and showed that in the property-testing regime it is possible to test @math -freeness for any graph @math of size 4 in constant time, @math rounds, regardless of the network size. However, Fraigniaud et. al. also showed that their techniques for graphs @math of size 4 cannot test @math -cycle-freeness in constant time. In this paper we revisit the subgraph-freeness problem and show that @math -cycle-freeness, and indeed @math -freeness for many other graphs @math comprising more than 4 vertices, can be tested in constant time. We show that @math -freeness can be tested in @math rounds for any cycle @math , improving on the running time of @math of the previous algorithms for triangle-freeness and @math -freeness. In the special case of triangles, we show that triangle-freeness can be solved in @math rounds independently of @math , when @math is not too small with respect to the number of nodes and edges. We also show that @math -freeness for any constant-size tree @math can be tested in @math rounds, even without the property-testing relaxation. Building on these results, we define a general class of graphs for which we can test subgraph-freeness in @math rounds. This class includes all graphs over 5 vertices except the 5-clique, @math . For cliques @math over @math nodes, we show that @math -freeness can be tested in @math rounds, where @math is the number of edges. We show a new way to round vector solutions of semidefinite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum of the input graph. We demonstrate the utility of our method by providing a new SDP-hierarchy based algorithm for constraint satisfaction problems with 2-variable constraints (2-CSP's). More concretely, we show for every 2-CSP instance I a rounding algorithm for r rounds of the Lasserre SDP hierarchy for I that obtains an integral solution that is at most worse than the relaxation's value (normalized to lie in [0,1]), as long as r > k ( ) ( ) ;, where k is the alphabet size of I, @math , and @math denotes the number of eigenvalues larger than @math in the normalized adjacency matrix of the constraint graph of @math . In the case that @math is a instance, the threshold @math is only a polynomial in @math , and is independent of the alphabet size. Also in this case, we can give a non-trivial bound on the number of rounds for instance. In particular our result yields an SDP-hierarchy based algorithm that matches the performance of the recent subexponential algorithm of Arora, Barak and Steurer (FOCS 2010) in the worst case, but runs faster on a natural family of instances, thus further restricting the set of possible hard instances for Khot's Unique Games Conjecture. Our algorithm actually requires less than the @math constraints specified by the @math level of the Lasserre hierarchy, and in some cases @math rounds of our program can be evaluated in time @math . We present a simple distributed @math -approximation algorithm for maximum weight independent set (MaxIS) in the @math model which completes in @math rounds, where @math is the maximum degree, @math is the number of rounds needed to compute a maximal independent set (MIS) on @math , and @math is the maximum weight of a node. Whether our algorithm is randomized or deterministic depends on the MIS algorithm used as a black-box. Plugging in the best known algorithm for MIS gives a randomized solution in @math rounds, where @math is the number of nodes. We also present a deterministic @math -round algorithm based on coloring. We then show how to use our MaxIS approximation algorithms to compute a @math -approximation for maximum weight matching without incurring any additional round penalty in the @math model. We use a known reduction for simulating algorithms on the line graph while incurring congestion, but we show our algorithm is part of a broad family of for which we describe a mechanism that allows the simulation to run in the @math model without an additional overhead. Next, we show that for maximum weight matching, relaxing the approximation factor to ( @math ) allows us to devise a distributed algorithm requiring @math rounds for any constant @math . For the unweighted case, we can even obtain a @math -approximation in this number of rounds. These algorithms are the first to achieve the provably optimal round complexity with respect to dependency on @math . We study a statistical model for the tensor principal component analysis problem introduced by Montanari and Richard: Given a order- @math tensor @math of the form @math , where @math is a signal-to-noise ratio, @math is a unit vector, and @math is a random noise tensor, the goal is to recover the planted vector @math . For the case that @math has iid standard Gaussian entries, we give an efficient algorithm to recover @math whenever @math , and certify that the recovered vector is close to a maximum likelihood estimator, all with high probability over the random choice of @math . The previous best algorithms with provable guarantees required @math . In the regime @math , natural tensor-unfolding-based spectral relaxations for the underlying optimization problem break down (in the sense that their integrality gap is large). To go beyond this barrier, we use convex relaxations based on the sum-of-squares method. Our recovery algorithm proceeds by rounding a degree- @math sum-of-squares relaxations of the maximum-likelihood-estimation problem for the statistical model. To complement our algorithmic results, we show that degree- @math sum-of-squares relaxations break down for @math , which demonstrates that improving our current guarantees (by more than logarithmic factors) would require new techniques or might even be intractable. Finally, we show how to exploit additional problem structure in order to solve our sum-of-squares relaxations, up to some approximation, very efficiently. Our fastest algorithm runs in nearly-linear time using shifted (matrix) power iteration and has similar guarantees as above. The analysis of this algorithm also confirms a variant of a conjecture of Montanari and Richard about singular vectors of tensor unfoldings. We present a near-optimal distributed algorithm for @math -approximation of single-commodity maximum flow in undirected weighted networks that runs in @math communication rounds in the model. Here, @math and @math denote the number of nodes and the network diameter, respectively. This is the first improvement over the trivial bound of @math , and it nearly matches the @math round complexity lower bound. The development of the algorithm contains two results of independent interest: (i) A @math -round distributed construction of a spanning tree of average stretch @math . (ii) A @math -round distributed construction of an @math -congestion approximator consisting of the cuts induced by @math virtual trees. The distributed representation of the cut approximator allows for evaluation in @math rounds. All our algorithms make use of randomization and succeed with high probability. We study the following one-person game against a random graph process: the Player's goal is to @math -colour a random sequence of edges @math of a complete graph on @math vertices, avoiding a monochromatic triangle for as long as possible. The game is over when a monochromatic triangle is created. The online version of the game requires that the Player should colour each edge as it comes, before looking at the next edge.While it is not hard to prove that the expected length of this game is about @math , the proof of the upper bound suggests the following relaxation: instead of colouring online, the random graph is generated in only two rounds, and the Player colours the edges of the first round before the edges of the second round are thrown in. Given the size of the first round, how many edges can there be in the second round for the Player to be likely to win? In the extreme case, when the first round consists of a random graph with @math edges, where @math is a positive constant, we show that the Player can win with high probability only if constantly many edges are generated in the second round. We give an approximation algorithm for non-uniform sparsest cut with the following guarantee: For any @math , given cost and demand graphs with edge weights @math respectively, we can find a set @math with @math at most @math times the optimal non-uniform sparsest cut value, in time @math provided @math . Here @math is the @math 'th smallest generalized eigenvalue of the Laplacian matrices of cost and demand graphs; @math (resp. @math ) is the weight of edges crossing the @math cut in cost (resp. demand) graph and @math is the sparsity of the optimal cut. In words, we show that the non-uniform sparsest cut problem is easy when the generalized spectrum grows moderately fast. To the best of our knowledge, there were no results based on higher order spectra for non-uniform sparsest cut prior to this work. Even for uniform sparsest cut, the quantitative aspects of our result are somewhat stronger than previous methods. Similar results hold for other expansion measures like edge expansion, normalized cut, and conductance, with the @math 'th smallest eigenvalue of the normalized Laplacian playing the role of @math in the latter two cases. Our proof is based on an l1-embedding of vectors from a semi-definite program from the Lasserre hierarchy. The embedded vectors are then rounded to a cut using standard threshold rounding. We hope that the ideas connecting @math -embeddings to Lasserre SDPs will find other applications. Another aspect of the analysis is the adaptation of the column selection paradigm from our earlier work on rounding Lasserre SDPs [GS11] to pick a set of edges rather than vertices. This feature is important in order to extend the algorithms to non-uniform sparsest cut. Clustering is a fundamental tool in data mining. It partitions points into groups (clusters) and may be used to make decisions for each point based on its group. However, this process may harm protected (minority) classes if the clustering algorithm does not adequately represent them in desirable clusters -- especially if the data is already biased. At NIPS 2017, proposed a model for fair clustering requiring the representation in each cluster to (approximately) preserve the global fraction of each protected class. Restricting to two protected classes, they developed both a 4-approximation for the fair @math -center problem and a @math -approximation for the fair @math -median problem, where @math is a parameter for the fairness model. For multiple protected classes, the best known result is a 14-approximation for fair @math -center. We extend and improve the known results. Firstly, we give a 5-approximation for the fair @math -center problem with multiple protected classes. Secondly, we propose a relaxed fairness notion under which we can give bicriteria constant-factor approximations for all of the classical clustering objectives @math -center, @math -supplier, @math -median, @math -means and facility location. The latter approximations are achieved by a framework that takes an arbitrary existing unfair (integral) solution and a fair (fractional) LP solution and combines them into an essentially fair clustering with a weakly supervised rounding scheme. In this way, a fair clustering can be established belatedly, in a situation where the centers are already fixed. This paper studies the lattice agreement problem and the generalized lattice agreement problem in distributed message passing systems. In the lattice agreement problem, given input values from a lattice, processes have to non-trivially decide output values that lie on a chain. We consider the lattice agreement problem in both synchronous and asynchronous systems. For synchronous lattice agreement, we present two algorithms which run in @math and @math rounds, respectively, where @math denotes the height of the input sublattice @math , @math is the number of crash failures the system can tolerate, and @math is the number of processes in the system. These algorithms have significant better round complexity than previously known algorithms. The algorithm by attiya1995atomic takes @math synchronous rounds, and the algorithm by Mavronicolasa mavronicolasabound takes @math rounds. For asynchronous lattice agreement, we propose an algorithm which has time complexity of @math message delays which improves on the previously known time complexity of @math message delays. The generalized lattice agreement problem defined by in faleiro2012generalized is a generalization of the lattice agreement problem where it is applied for the replicated state machine. We propose an algorithm which guarantees liveness when a majority of the processes are correct in asynchronous systems. Our algorithm requires @math units of time in the worst case which is better than @math units of time required by the algorithm of faleiro2012generalized . We consider the problem of finding a minimum edge cost subgraph of a graph satisfying both given node-connectivity requirements and degree upper bounds on nodes. We present an iterative rounding algorithm of the biset linear programming relaxation for this problem. For directed graphs and @math -out-connectivity requirements from a root, our algorithm computes a solution that is a 2-approximation on the cost, and the degree of each node @math in the solution is at most @math , where @math is the degree upper bound on @math . For undirected graphs and element-connectivity requirements with maximum connectivity requirement @math , our algorithm computes a solution that is a @math -approximation on the cost, and the degree of each node @math in the solution is at most @math . These ratios improve the previous @math -approximation on the cost and @math -approximation on the degrees. Our algorithms can be used to improve approximation ratios for other node-connectivity problems such as undirected $k... One of the fundamental clustering problems is to assign @math points into @math clusters based on minimal sum-of-squared distances (MSSC), which is known to be NP-hard. In this paper, by using matrix arguments, we first model MSSC as a so-called 0-1 semidefinite programming (SDP) problem. We show that our 0-1 SDP model provides a unified framework for several clustering approaches such as normalized k-cut and spectral clustering. Moreover, the 0-1 SDP model allows us to solve the underlying problem approximately via the linear programming and SDP relaxations. Second, we consider the issue of how to extract a feasible solution of the original 0-1 SDP model from the optimal solution of the relaxed SDP problem. By using principal component analysis, we develop a rounding procedure to construct a feasible partitioning from a solution of the relaxed problem. In our rounding procedure, we need to solve a K-means clustering problem in @math , which can be done in @math time. In case of biclustering, the running time of our rounding procedure can be reduced to @math . We show that our algorithm provides a 2-approximate solution to the original problem. Promising numerical results for biclustering based on our new method are reported. Random constraint satisfaction problems (CSPs) are known to exhibit threshold phenomena: given a uniformly random instance of a CSP with @math variables and @math clauses, there is a value of @math beyond which the CSP will be unsatisfiable with high probability. Strong refutation is the problem of certifying that no variable assignment satisfies more than a constant fraction of clauses; this is the natural algorithmic problem in the unsatisfiable regime (when @math ). Intuitively, strong refutation should become easier as the clause density @math grows, because the contradictions introduced by the random clauses become more locally apparent. For CSPs such as @math -SAT and @math -XOR, there is a long-standing gap between the clause density at which efficient strong refutation algorithms are known, @math , and the clause density at which instances become unsatisfiable with high probability, @math . In this paper, we give spectral and sum-of-squares algorithms for strongly refuting random @math -XOR instances with clause density @math in time @math or in @math rounds of the sum-of-squares hierarchy, for any @math and any integer @math . Our algorithms provide a smooth transition between the clause density at which polynomial-time algorithms are known at @math , and brute-force refutation at the satisfiability threshold when @math . We also leverage our @math -XOR results to obtain strong refutation algorithms for SAT (or any other Boolean CSP) at similar clause densities. Our algorithms match the known sum-of-squares lower bounds due to Grigoriev and Schonebeck, up to logarithmic factors. Additionally, we extend our techniques to give new results for certifying upper bounds on the injective tensor norm of random tensors. Several algorithms with an approximation guarantee of @math are known for the Set Cover problem, where @math is the number of elements. We study a generalization of the Set Cover problem, called the Partition Set Cover problem. Here, the elements are partitioned into @math , and we are required to cover at least @math elements from each color class @math , using the minimum number of sets. We give a randomized LP-rounding algorithm that is an @math approximation for the Partition Set Cover problem. Here @math denotes the approximation guarantee for a related Set Cover instance obtained by rounding the standard LP. As a corollary, we obtain improved approximation guarantees for various set systems for which @math is known to be sublogarithmic in @math . We also extend the LP rounding algorithm to obtain @math approximations for similar generalizations of the Facility Location type problems. Finally, we show that many of these results are essentially tight, by showing that it is NP-hard to obtain an @math -approximation for any of these problems. In this paper we study the approximation algorithms for a class of discrete quadratic optimization problems in the Hermitian complex form. A special case of the problem that we study corresponds to the max-3-cut model used in a recent paper of Goemans and Williamson J. Comput. System Sci., 68 (2004), pp. 442-470]. We first develop a closed-form formula to compute the probability of a complex-valued normally distributed bivariate random vector to be in a given angular region. This formula allows us to compute the expected value of a randomized (with a specific rounding rule) solution based on the optimal solution of the complex semidefinite programming relaxation problem. In particular, we present an @math -approximation algorithm, and then study the limit of that model, in which the problem remains NP-hard. We show that if the objective is to maximize a positive semidefinite Hermitian form, then the randomization-rounding procedure guarantees a worst-case performance ratio of @math , which is better than the ratio of @math for its counterpart in the real case due to Nesterov. Furthermore, if the objective matrix is real-valued positive semidefinite with nonpositive off-diagonal elements, then the performance ratio improves to 0.9349. We present simple deterministic algorithms for subgraph finding and enumeration in the broadcast CONGEST model of distributed computation: -- For any constant @math , detecting @math -paths and trees on @math nodes can be done in constantly many rounds, and @math -cycles in @math rounds. -- On @math -degenerate graphs, cliques and @math -cycles can be enumerated in @math rounds, and @math -cycles in @math rounds. In many cases, these bounds are tight up to logarithmic factors. Moreover, we show that the algorithms for @math -degenerate graphs can be improved to optimal complexity @math and @math , respectively, in the supported CONGEST model, which can be seen as an intermediate model between CONGEST and the congested clique. By prior work, there is a distributed graph algorithm that finds a maximal fractional matching (maximal edge packing) in @math O(Δ) rounds, independently of @math n; here @math Δ is the maximum degree of the graph and @math n is the number of nodes in the graph. We show that this is optimal: there is no distributed algorithm that finds a maximal fractional matching in @math o(Δ) rounds, independently of @math n. Our work gives the first linear-in- @math Δ lower bound for a natural graph problem in the standard @math LOCAL model of distributed computing--prior lower bounds for a wide range of graph problems have been at best logarithmic in @math Δ. Guruswami and Sinop give a @math approximation guarantee for the non-uniform Sparsest Cut problem by solving @math -level Lasserre semidefinite constraints, provided that the generalized eigenvalues of the Laplacians of the cost and demand graphs satisfy a certain spectral condition, namely, @math . Their key idea is a rounding technique that first maps a vector-valued solution to @math using appropriately scaled projections onto Lasserre vectors. In this paper, we show that similar projections and analysis can be obtained using only @math triangle inequality constraints. This results in a @math approximation guarantee for the non-uniform Sparsest Cut problem by adding only @math triangle inequality constraints to the usual semidefinite program, provided that the same spectral condition, @math , holds. In this paper we present distributed testing algorithms of graph properties in the CONGEST-model [Censor- 2016]. We present one-sided error testing algorithms in the general graph model. We first describe a general procedure for converting @math -testers with a number of rounds @math , where @math denotes the diameter of the graph, to @math rounds, where @math is the number of processors of the network. We then apply this procedure to obtain an optimal tester, in terms of @math , for testing bipartiteness, whose round complexity is @math , which improves over the @math -round algorithm by Censor- (DISC 2016). Moreover, for cycle-freeness, we obtain a of the graph that locally corrects the graph so that the corrected graph is acyclic. Note that, unlike a tester, a corrector needs to mend the graph in many places in the case that the graph is far from having the property. In the second part of the paper we design algorithms for testing whether the network is @math -free for any connected @math of size up to four with round complexity of @math . This improves over the @math -round algorithms for testing triangle freeness by Censor- (DISC 2016) and for testing excluded graphs of size @math by (DISC 2016). In the last part we generalize the global tester by Iwama and Yoshida (ITCS 2014) of testing @math -path freeness to testing the exclusion of any tree of order @math . We then show how to simulate this algorithm in the CONGEST-model in @math rounds.