Source author record

Patrick Lin

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Computational Complexity Machine Learning math.MG math.OC

Catalog footprint

Research overview

4works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A Toroidal Maxwell-Cremona-Delaunay Correspondence

We consider three classes of geodesic embeddings of graphs on Euclidean flat tori: (1) A toroidal graph embedding $Γ$ is positive equilibrium if it is possible to place positive weights on the edges, such that the weighted edge vectors incident to each vertex of $Γ$ sum to zero. (2) A toroidal graph embedding $Γ$ is reciprocal if there is a geodesic embedding $Γ^*$ of its dual on the same flat torus, where each edge of $Γ$ is orthogonal to the corresponding dual edge in $Γ^*$ . (3) A toroidal graph embedding $Γ$ is coherent if it is possible to assign weights to the vertices, so that $Γ$ is the (intrinsic) weighted Delaunay graph of its vertices. The classical Maxwell-Cremona correspondence and the well-known correspondence between convex hulls and weighted Delaunay triangulations imply that the analogous concepts for planar graph embeddings (with convex outer faces) are equivalent. Indeed, all three conditions are equivalent to $Γ$ being the projection of the 1-skeleton of the lower convex hull of points in $\mathbb{R}^3$ . However, this three-way equivalence does not extend directly to geodesic graph embeddings on flat tori. On any flat torus, reciprocal and coherent embeddings are equivalent, and every reciprocal embedding is in positive equilibrium, but not every positive equilibrium embedding is reciprocal. We establish a weaker correspondence: Every positive equilibrium embedding on any flat torus is affinely equivalent to a reciprocal/coherent embedding on some flat torus.

preprint2020arXiv

How to Morph Graphs on the Torus

We present the first algorithm to morph graphs on the torus. Given two isotopic essentially 3-connected embeddings of the same graph on the Euclidean flat torus, where the edges in both drawings are geodesics, our algorithm computes a continuous deformation from one drawing to the other, such that all edges are geodesics at all times. Previously even the existence of such a morph was not known. Our algorithm runs in $O(n^{1+ω/2})$ time, where $ω$ is the matrix multiplication exponent, and the computed morph consists of $O(n)$ parallel linear morphing steps. Existing techniques for morphing planar straight-line graphs do not immediately generalize to graphs on the torus; in particular, Cairns' original 1944 proof and its more recent improvements rely on the fact that every planar graph contains a vertex of degree at most 5. Our proof relies on a subtle geometric analysis of 6-regular triangulations of the torus. We also make heavy use of a natural extension of Tutte's spring embedding theorem to torus graphs.

preprint2016arXiv

Scenario Submodular Cover

Many problems in Machine Learning can be modeled as submodular optimization problems. Recent work has focused on stochastic or adaptive versions of these problems. We consider the Scenario Submodular Cover problem, which is a counterpart to the Stochastic Submodular Cover problem studied by Golovin and Krause. In Scenario Submodular Cover, the goal is to produce a cover with minimum expected cost, where the expectation is with respect to an empirical joint distribution, given as input by a weighted sample of realizations. In contrast, in Stochastic Submodular Cover, the variables of the input distribution are assumed to be independent, and the distribution of each variable is given as input. Building on algorithms developed by Cicalese et al. and Golovin and Krause for related problems, we give two approximation algorithms for Scenario Submodular Cover over discrete distributions. The first achieves an approximation factor of O(log Qm), where m is the size of the sample and Q is the goal utility. The second, simpler algorithm achieves an approximation bound of O(log QW), where Q is the goal utility and W is the sum of the integer weights. (Both bounds assume an integer-valued utility function.) Our results yield approximation bounds for other problems involving non-independent distributions that are explicitly specified by their support.

preprint2015arXiv

Discrete Stochastic Submodular Maximization: Adaptive vs. Non-Adaptive vs. Offline

We consider the problem of stochastic monotone submodular function maximization, subject to constraints. We give results on adaptivity gaps, and on the gap between the optimal offline and online solutions. We present a procedure that transforms a decision tree (adaptive algorithm) into a non-adaptive chain. We prove that this chain achieves at least $τ$ times the utility of the decision tree, over a product distribution and binary state space, where $τ = \min_{i,j} \Pr[x_i=j]$ . This proves an adaptivity gap of $1/τ$ (which is $2$ in the case of a uniform distribution) for the problem of stochastic monotone submodular maximization subject to state-independent constraints. For a cardinality constraint, we prove that a simple adaptive greedy algorithm achieves an approximation factor of $(1-1/e^τ)$ with respect to the optimal offline solution; previously, it has been proven that the algorithm achieves an approximation factor of $(1-1/e)$ with respect to the optimal adaptive online solution. Finally, we show that there exists a non-adaptive solution for the stochastic max coverage problem that is within a factor $(1-1/e)$ of the optimal adaptive solution and within a factor of $τ(1-1/e)$ of the optimal offline solution.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.