More Like this

1. A Dynamic Programming Framework for Generating Approximately Diverse and Optimal Solutions

   Gálvez, Waldo; Goswami, Mayank; Merino, Arturo; Park, GiBeom; Tsai, Meng-Tsung; Verdugo, Victor (January 2025, Arxiv)

   We develop a general framework, called approximately-diverse dynamic programming (ADDP) that can be used to generate a collection of k≥2 maximally diverse solutions to various geometric and combinatorial optimization problems. Given an approximation factor 0≤c≤1, this framework also allows for maximizing diversity in the larger space of c-approximate solutions. We focus on two geometric problems to showcase this technique: 1. Given a polygon P, an integer k≥2 and a value c≤1, generate k maximally diverse c-nice triangulations of P. Here, a c-nice triangulation is one that is c-approximately optimal with respect to a given quality measure σ. 2. Given a planar graph G, an integer k≥2 and a value c≤1, generate k maximally diverse c-optimal Independent Sets (or, Vertex Covers). Here, an independent set S is said to be c-optimal if |S|≥c|S′| for any independent set S′ of G. Given a set of k solutions to the above problems, the diversity measure we focus on is the average distance between the solutions, where d(X,Y)=|XΔY|. For arbitrary polygons and a wide range of quality measures, we give poly(n,k) time (1−Θ(1/k))-approximation algorithms for the diverse triangulation problem. For the diverse independent set and vertex cover problems on planar graphs, we give an algorithm that runs in time 2^(O(k.δ^(−1).ϵ^(−2)).n^O(1/ϵ) and returns (1−ϵ)-approximately diverse (1−δ)c-optimal independent sets or vertex covers. Our triangulation results are the first algorithmic results on computing collections of diverse geometric objects, and our planar graph results are the first PTAS for the diverse versions of any NP-complete problem. Additionally, we also provide applications of this technique to diverse variants of other geometric problems. 

   more » « less
2. Integer coordinates for intrinsic geometry processing

   https://doi.org/10.1145/3478513.3480522  

   Gillespie, Mark; Sharp, Nicholas; Crane, Keenan (December 2021, ACM Transactions on Graphics)

   This paper describes a numerically robust data structure for encoding intrinsic triangulations of polyhedral surfaces. Many applications demand a correspondence between the intrinsic triangulation and the input surface, but existing data structures either rely on floating point values to encode correspondence, or do not support remeshing operations beyond basic edge flips. We instead provide an integer-based data structure that guarantees valid correspondence, even for meshes with near-degenerate elements. Our starting point is the framework ofnormal coordinatesfrom geometric topology, which we extend to the broader set of operations needed for mesh processing (vertex insertion, edge splits,etc.). The resulting data structure can be used as a drop-in replacement for earlier schemes, automatically improving reliability across a wide variety of applications. As a stress test, we successfully compute an intrinsic Delaunay refinement and associated subdivision for all manifold meshes in the Thingi10k dataset. In turn, we can compute reliable and highly accurate solutions to partial differential equations even on extremely low-quality meshes. 

   more » « less
3. Discrete conformal equivalence of polyhedral surfaces

   https://doi.org/10.1145/3450626.3459763  

   Gillespie, Mark; Springborn, Boris; Crane, Keenan (July 2021, ACM Transactions on Graphics)

   This paper describes a numerical method for surface parameterization, yielding maps that are locally injective and discretely conformal in an exact sense. Unlike previous methods for discrete conformal parameterization, the method is guaranteed to work for any manifold triangle mesh, with no restrictions on triangulatiothat each task can be formulated as a convex problem where the triangulation is allowed to change---we complete the picture by introducing the machinery needed to actually construct a discrete conformal map. In particular, we introduce a new scheme for tracking correspondence between triangulations based onnormal coordinates, and a new interpolation procedure based on layout in thelight cone.Stress tests involving difficult cone configurations and near-degenerate triangulations indicate that the method is extremely robust in practice, and provides high-quality interpolation even on meshes with poor elements. 

   more » « less
4. Online Balanced Allocation of Dynamic Components

   https://doi.org/10.4230/lipics.itcs.2025.81  

   Rajaraman, Rajmohan; Wasim, Omer (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   We introduce Online Balanced Allocation of Dynamic Components (OBADC), a problem motivated by the practical challenge of dynamic resource allocation for large-scale distributed applications. In OBADC, we need to allocate a dynamic set of at most k𝓁 vertices (representing processes) in 𝓁 > 0 clusters. We consider an over-provisioned setup in which each cluster can hold at most k(1+ε) vertices, for an arbitrary constant ε > 0. The communication requirements among the vertices are modeled by the notion of a dynamically changing component, which is a subset of vertices that need to be co-located in the same cluster. At each time t, a request r_t of one of the following types arrives: 1) insertion of a vertex v forming a singleton component v at unit cost. 2) merge of (u,v) requiring that the components containing u and v be merged and co-located thereafter. 3) deletion of an existing vertex v at zero cost. Before serving any request, an algorithm can migrate vertices from one cluster to another, at a unit migration cost per vertex. We seek an online algorithm to minimize the total migration cost incurred for an arbitrary request sequence σ = (r_t)_{t > 0}, while simultaneously minimizing the number of clusters utilized. We analyze competitiveness with respect to an optimal clairvoyant offline algorithm with identical (over-provisioned) capacity constraints. We give an O(log k)-competitive algorithm for OBADC, and a matching lower-bound. The number of clusters utilized by our algorithm is always within a (2+ε) factor of the minimum. Furthermore, in a resource augmented setting where the optimal offline algorithm is constrained to capacity k per cluster, our algorithm obtains O(log k) competitiveness and utilizes a number of clusters within (1+ε) factor of the minimum. We also consider OBADC in the context of machine-learned predictions, where for each newly inserted vertex v at time t: i) with probability η > 0, the set of vertices (that exist at time t) in the component of v is revealed and, ii) with probability 1-η, no information is revealed. For OBADC with predictions, we give a O(1)-consistent and O(min(log 1/(η), log k))-robust algorithm. 

   more » « less
5. Random Graph Matching with Improved Noise Robustness

   Mao, Cheng; Rudelson, Mark; Tikhomirov, Konstantin (August 2021, Proceedings of Machine Learning Research)

   Belkin, Mikhail; Kpotufe, Samory (Ed.)

   Graph matching, also known as network alignment, refers to finding a bijection between the vertex sets of two given graphs so as to maximally align their edges. This fundamental computational problem arises frequently in multiple fields such as computer vision and biology. Recently, there has been a plethora of work studying efficient algorithms for graph matching under probabilistic models. In this work, we propose a new algorithm for graph matching: Our algorithm associates each vertex with a signature vector using a multistage procedure and then matches a pair of vertices from the two graphs if their signature vectors are close to each other. We show that, for two Erdős–Rényi graphs with edge correlation $$1-\alpha$$, our algorithm recovers the underlying matching exactly with high probability when $$\alpha \le 1 / (\log \log n)^C$$, where $$n$$ is the number of vertices in each graph and $$C$$ denotes a positive universal constant. This improves the condition $$\alpha \le 1 / (\log n)^C$$ achieved in previous work. 

   more » « less