Search for: All records

The greedy and nearest-neighbor TSP heuristics can both have $$\log n$$ approximation factors from optimal in worst case, even just for $$n$$ points in Euclidean space. In this note, we show that this approximation factor is only realized when the optimal tour is unusually short. In particular, for points from any fixed $$d$$-Ahlfor's regular metric space (which includes any $$d$$-manifold like the $$d$$-cube $[0,1]^d$ in the case $$d$$ is an integer but also fractals of dimension $$d$$ when $$d$$ is real-valued), our results imply that the greedy and nearest-neighbor heuristics have additive errors from optimal on the order of the optimal tour length through random points in the same space, for $d>1$. 

We prove that a polynomial fraction of the set of $$k$$-component forests in the $$m \times n$$ grid graph have equal numbers of vertices in each component, for any constant $$k$$. This resolves a conjecture of Charikar, Liu, Liu, and Vuong, and establishes the first provably polynomial-time algorithm for (exactly or approximately) sampling balanced grid graph partitions according to the spanning tree distribution, which weights each $$k$$-partition according to the product, across its $$k$$ pieces, of the number of spanning trees of each piece. Our result follows from a careful analysis of the probability a uniformly random spanning tree of the grid can be cut into balanced pieces. Beyond grids, we show that for a broad family of lattice-like graphs, we achieve balance up to any multiplicative $$(1 \pm \varepsilon)$$ constant with constant probability. More generally, we show that, with constant probability, components derived from uniform spanning trees can approximate any given partition of a planar region specified by Jordan curves. This implies polynomial-time algorithms for sampling approximately balanced tree-weighted partitions for lattice-like graphs. Our results have applications to understanding political districtings, where there is an underlying graph of indivisible geographic units that must be partitioned into $$k$$ population-balanced connected subgraphs. In this setting, tree-weighted partitions have interesting geometric properties, and this has stimulated significant effort to develop methods to sample them. 

We show that if an open set in $$\mathbb R^d$$ can be fibered by unit $$n$$-spheres, then $$d\le 2n+1$$, and if $d=2n+1$, then the spheres must be pairwise linked, and $$n\in \{0,1,3,7\}$$. For these values of $$n$$, we construct unit $$n$$-sphere fibrations in $$R^{2n+1}$$. 

Let $$N=\binom{n}{2}$$ and $$s\geq 2$$. Let $$e_{i,j},\,i=1,2,\ldots,N,\,j=1,2,\ldots,s$$ be $$s$$ independent permutations of the edges $$E(K_n)$$ of the complete graph $$K_n$$. A MultiTree is a set $$I\subseteq [N]$$ such that the edge sets $$E_{I,j}$$ induce spanning trees for $$j=1,2,\ldots,s$$. In this paper we study the following question: what is the smallest $m=m(n)$ such that w.h.p. $[m]$ contains a MultiTree. We prove a hitting time result for $s=2$ and an $$O(n\log n)$$ bound for $$s\geq 3$$.