Simple heuristics often show a remarkable performance in practice for optimization problems. Worst-case analysis often falls short of explaining this performance. Because of this, "beyond worst-case analysis" of algorithms has recently gained a lot of attention, including probabilistic analysis of algorithms. The instances of many optimization problems are essentially a discrete metric space. Probabilistic analysis for such metric optimization problems has nevertheless mostly been conducted on instances drawn from Euclidean space, which provides a structure that is usually heavily exploited in the analysis. However, most instances from practice are not Euclidean. Little work has been done on metric instances drawn from other, more realistic, distributions. Some initial results have been obtained by (Algorithmica, 2013), who have used random shortest path metrics on complete graphs to analyze heuristics. The goal of this paper is to generalize these findings to non-complete graphs, especially Erdős-Renyi random graphs. A random shortest path metric is constructed by drawing independent random edge weights for each edge in the graph and setting the distance between every pair of vertices to the length of a shortest path between them with respect to the drawn weights. For such instances, we prove that the greedy heuristic for the minimum distance maximum matching problem, the nearest neighbor and insertion heuristics for the traveling salesman problem, and a trivial heuristic for the @math -median problem all achieve a constant expected approximation ratio. Additionally, we show a polynomial upper bound for the expected number of iterations of the 2-opt heuristic for the traveling salesman problem.
called the model described above . This model is also known as , introduced by Hammersley and Welsh as a model for fluid flow through a (random) porous medium @cite_0 @cite_7 . For first passage percolation in complete graphs, the expected distance between two fixed vertices is approximately @math and the expected distance from a fixed vertex to the vertex that is most distant is approximately @math @cite_1 @cite_8 . Furthermore, the expected diameter of the metric is approximately @math @cite_10 @cite_8 . There are also some known structural properties of first passage percolation on the Erd o s--R 'enyi random graph. @cite_2 have shown asymptotics for both the minimal weight of the path between uniformly chosen vertices in the giant component and for the hopcount, the number of edges, on this path. @cite_1 used this model on the complete graph to analyze heuristics for matching, TSP, and @math -median.
@cite_7 @cite_8 @cite_1 @cite_0 @cite_2 @cite_10
2946854362 2903855202 2950901863 2005443809
In this paper we explore first passage percolation (FPP) on the Erd˝ os-Renyi random graph Gn(pn), where each edge is given an independent exponential edge weight with rate 1. In the sparse regime, i.e., when npn → λ > 1, we find refined asymptotics both for the minimal weight of the path between uniformly chosen vertices in the giant component, as well as for the hopcount (i.e., the number of edges) on this minimal weight path. More precisely, we prove a central limit theorem for the hopcount, with asymptotic mean and variance both equal to λ (λ − 1) log n. Furthermore, we prove that the minimal weight centered by log n (λ − 1) converges in distribution. We also investigate the dense regime, where npn → ∞. We find that although the base graph is a ultra small (meaning that graph distances between uniformly chosen vertices are o(log n)), attaching random edge weights changes the geometry of the network completely. Indeed, the hopcount Hn satisfies the universality property that whatever be the value of pn, Hn log n → 1 in probability and, more precisely, (Hn−βn log n) √ log n, where βn = λn (λn− 1), has a limiting standard normal distribution. The constant βn can be replaced by 1 precisely when λn ≫ √ log n, a case that has appeared in the literature (under stronger conditions on λn) in (2, 12). We also find bounds for the maximal weight and maximal hopcount between vertices in the graph. This paper continues the investigation of FPP initiated in (2) and (3). Compared to the setting on the configuration model studied in (3), the proofs presented here are much simpler due to a direct relation between FPP on the Erd˝ os-Renyi random graph and thinned continuous-time branching processes. Abstract In this paper a random graph model G Z N 2 , p d is introduced, which is a combination of fixed torus grid edges in ( Z ∕ N Z ) 2 and some additional random ones. The random edges are called long, and the probability of having a long edge between vertices u , v ∈ ( Z ∕ N Z ) 2 with graph distance d on the torus grid is p d = c ∕ N d , where c is some constant. We show that, whp, the diameter D ( G Z N 2 , p d ) = Θ ( log N ) . Moreover, we consider a modified non-monotonous bootstrap percolation on G Z N 2 , p d . We prove the presence of phase transitions in mean-field approximation and provide fairly sharp bounds on the error of the critical parameters. We consider two competing first passage percolation processes started from uniformly chosen subsets of a random regular graph on @math vertices. The processes are allowed to spread with different rates, start from vertex subsets of different sizes or at different times. We obtain tight results regarding the sizes of the vertex sets occupied by each process, showing that in the generic situation one process will occupy @math vertices, for some @math . The value of @math is calculated in terms of the relative rates of the processes, as well as the sizes of the initial vertex sets and the possible time advantage of one process. The motivation for this work comes from the study of viral marketing on social networks. The described processes can be viewed as two competing products spreading through a social network (random regular graph). Considering the processes which grow at different rates (corresponding to different attraction levels of the two products) or starting at different times (the first to market advantage) allows to model aspects of real competition. The results obtained can be interpreted as one of the two products taking the lion share of the market. We compare these results to the same process run on @math dimensional grids where we show that in the generic situation the two products will have a linear fraction of the market each. Percolation with edge-passage probability p and first-passage percolation are studied for the n-cube Bn = 0, 1 with nearest neighbor edges. For oriented and unoriented percolation, p = e n and p = 1 n are the respective critical probabilities. For oriented first-passage percolation with i.i.d. edge-passage times having a density of 1 near the origin, the percolation time (time to reach the opposite corner of the cube) converges in probability to 1 as n → ∞. This resolves a conjecture of David Aldous. When the edge-passage distribution is standard exponential, the (smaller) percolation time for unoriented edges is at least 0.88. These results are applied to Richardson’s model on the (unoriented) n-cube. Richardson’s model, otherwise known as the contact process with no recoveries, models the spread of infection as a Poisson process on each edge connecting an infected node to an uninfected one. It is shown that the time to cover the entire n-cube is bounded between 1.41 and 14.05 in probability as n→∞. Research supported by the National Security Agency under Grant Number MDA904-89-H-2051. Research supported by a National Science Foundation postdoctoral fellowship and by a Mathematical Sciences Institute postdoctoral fellowship. AMS 1991 subject classifications. Primary 60K35; secondary 60C05.