Author name cluster

Wesley Pegden

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

STOC Conference 2024 Conference Paper

Sampling Balanced Forests of Grids in Polynomial Time

Sarah Cannon
Wesley Pegden
Jamie Tucker-Foltz

We prove that a polynomial fraction of the set of k -component forests in the m × 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 ± ε) 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.

Details

SODA Conference 2023 Conference Paper

Subexponential mixing for partition chains on grid-like graphs

Alan M. Frieze
Wesley Pegden

We consider the problem of generating uniformly random partitions of the vertex set of a graph such that every piece induces a connected subgraph. For the case where we want to have partitions with linearly many pieces of bounded size, we obtain approximate sampling algorithms based on Glauber dynamics which are fixed-parameter tractable with respect to the bandwidth of G, with simple-exponential dependence on the bandwidth. For example, for rectangles of constant or logarithmic width this gives polynomial-time sampling algorithms. More generally, this gives sub-exponential algorithms for bounded-degree graphs without large expander sub-graphs (for example, we obtain time algorithms for square grids). In the case where we instead want partitions with a small number of pieces of linear size, we show that Glauber dynamics can have exponential mixing time, even just for the case of 2 pieces, and even for 2-connected sub-graphs of the grid with bounded bandwidth.

Details

UAI Conference 2020 Conference Paper

Semi-bandit Optimization in the Dispersed Setting

Travis Dick
Wesley Pegden
Maria-Florina Balcan

The goal of data-driven algorithm design is to obtain high-performing algorithms for specific application domains using machine learning and data. Across many fields in AI, science, and engineering, practitioners will often fix a family of parameterized algorithms and then optimize those parameters to obtain good performance on example instances from the application domain. In the online setting, we must choose algorithm parameters for each instance as they arrive, and our goal is to be competitive with the best fixed algorithm in hindsight.There are two major challenges in online data-driven algorithm design. First, it can be computationally expensive to evaluate the loss functions that map algorithm parameters to performance, which often require the learner to run a combinatorial algorithm to measure its performance. Second, the losses can be extremely volatile and have sharp discontinuities. However, we show that in many applications, evaluating the loss function for one algorithm choice can sometimes reveal the loss for a range of similar algorithms, essentially for free. We develop online optimization algorithms capable of using this kind of extra information by working in the semi-bandit feedback setting. Our algorithms achieve regret bounds that are essentially as good as algorithms under full-information feedback and are significantly more computationally efficient. We apply our semi-bandit results to obtain the first provable guarantees for data-driven algorithm design for linkage-based clustering and we improve the best regret bounds for designing greedy knapsack algorithms.

Details

SODA Conference 2019 Conference Paper

On the rank of a random binary matrix

Colin Cooper
Alan M. Frieze
Wesley Pegden

We study the rank of a random n × m matrix A n, m; k with entries from GF (2), and exactly k unit entries in each column, the other entries being zero. The columns are chosen independently and uniformly at random from the set of all ( n k ) such columns. We obtain an asymptotically correct estimate for the rank as a function of the number of columns m in terms of c, n, k, and where m = cn/k. The matrix A n, m; k forms the vertex-edge incidence matrix of a k -uniform random hypergraph H. The rank of A n, m; k can be expressed as follows. Let | C 2 | be the number of vertices of the 2-core of H, and | E ( C 2 )| the number of edges. Let m* be the value of m for which | C 2 | = | E ( C 2 )|. Then w. h. p. for m < m * the rank of A n, m; k is asymptotic to m, and for m ≥ m * the rank is asymptotic to m – | E ( C 2 )| + | C 2 |. In addition, assign i. i. d. U [0, 1] weights X i, i ∊ 1, 2, … m to the columns, and define the weight of a set of columns S as X ( S ) = ∑ j ∊ S X j. Define a basis as a set of n – 1 ( k even) linearly independent columns. We obtain an asymptotically correct estimate for the minimum weight basis. This generalises the well-known result of Frieze [On the value of a random minimum spanning tree problem, Discrete Applied Mathematics, (1985)] that, for k = 2, the expected length of a minimum weight spanning tree tends to ζ(3) ∼ 1. 202.

Details

STOC Conference 2016 Conference Paper

Separating subadditive euclidean functionals

Alan M. Frieze
Wesley Pegden

The classical Beardwood-Halton-Hammersly theorem (1959) asserts the existence of an asymptotic formula of the form constant times square root n for the minimum length of a Traveling Salesperson Tour through n random points in the unit square, and in the decades since it was proved, the existence of such formulas has been shown for other such Euclidean functionals on random points in the unit square as well. Despite more than 50 years of attention, however, it remained unknown whether the minimum length TSP through n random points in the unit square was asymptotically distinct from its natural lower bounds, such as the minimum length spanning tree, the minimum length 2-factor, or, as raised by Goemans and Bertsimas, from its linear programming relaxation. We prove that the TSP on random points in Euclidean space is indeed asymptotically distinct from these and other natural lower bounds, and show that this separation implies that branch-and-bound algorithms based on these natural lower bounds must take nearly exponential time to solve the TSP to optimality, even in average case. This is the first average-case superpolynomial lower bound for these branch-and-bound algorithms.

Details