Publications (8)
Parameterized Inapproximability of Exact Cover and Nearest Codeword
Venkatesan Guruswami, Patrick Lin
The -ExactCover problem is a parameterized version of the ExactCover problem, in which we are given a universe , a collection of subsets of , and an integer , and t…
A Note on Toroidal Maxwell-Cremona Correspondences
Patrick Lin
We explore toroidal analogues of the Maxwell-Cremona correspondence. Erickson and Lin [arXiv:2003.10057] showed the following correspondence for geodesic torus graphs : a positi…
Scenario Submodular Cover
Nathaniel Grammel, Lisa Hellerstein, Devorah Kletenik +1
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…
How to Morph Graphs on the Torus
Erin Wolf Chambers, Jeff Erickson, Patrick Lin +1
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…
A Toroidal Maxwell-Cremona-Delaunay Correspondence
Jeff Erickson, Patrick Lin
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 w…
Planar and Toroidal Morphs Made Easier
Jeff Erickson, Patrick Lin
We present simpler algorithms for two closely related morphing problems, both based on the barycentric interpolation paradigm introduced by Floater and Gotsman, which is in turn ba…