69 citations · 180 across the 32 of their papers we have counts for
40 papers
Query Complexity of Densest Sub(hyper)graph Problems
Sinan G. Aksoy, Eli Friedman, Nate Veldt +1
Rubinstein et al. introduce the study of connectivity and minimum cut problems in the cut query model, where an algorithm can only access the edges of a graph through CUT queries.…
An Improved Combinatorial Algorithm for Edge-Colored Clustering in Hypergraphs
Seongjune Han, Nate Veldt
Many complex systems and datasets are characterized by multiway interactions of different categories, and can be modeled as edge-colored hypergraphs. We focus on clustering such da…
Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion
Nate Veldt, Thomas Stanley, Benjamin W. Priest +5
We present improved learning-augmented algorithms for finding an approximate minimum spanning tree (MST) for points in an arbitrary metric space. Our work follows a recent framewor…
A Simple and Fast -approximation for Constrained Correlation Clustering
Nate Veldt
In Constrained Correlation Clustering, the goal is to cluster a complete signed graph in a way that minimizes the number of negative edges inside clusters plus the number of positi…
The Densest SWAMP problem: subhypergraphs with arbitrary monotonic partial edge rewards
Vedangi Bengali, Nikolaj Tatti, Iiro Kumpulainen +2
We consider a generalization of the densest subhypergraph problem where nonnegative rewards are given for including partial hyperedges in a dense subhypergraph. Prior work addresse…
Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Alex Crane, Thomas Stanley, Blair D. Sullivan +1
We consider a framework for clustering edge-colored hypergraphs, where the goal is to cluster (equivalently, to color) objects based on the primary type of multiway interactions th…
Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees
Nate Veldt, Thomas Stanley, Benjamin W. Priest +4
Finding a minimum spanning tree (MST) for points in an arbitrary metric space is a fundamental primitive for hierarchical clustering and many other ML tasks, but this takes $Ω(…
On the tractability and approximability of non-submodular cardinality-based - cut problems in hypergraphs
Vedangi Bengali, Nate Veldt
A minimum - cut in a hypergraph is a bipartition of vertices that separates two nodes and while minimizing a hypergraph cut function. The cardinality-based hypergraph…
Improved Hardness and Approximations for Cardinality-Based Minimum - Cuts Problems in Hypergraphs
Florian Adriaens, Vedangi Bengali, Iiro Kumpulainen +2
In hypergraphs, an edge that crosses a cut (i.e., a bipartition of nodes) can be split in several ways, depending on how many nodes are placed on each side of the cut. A cardinalit…
Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better
Vicente Balmaseda, Ying Xu, Yixin Cao +1
Cluster deletion is an NP-hard graph clustering objective with applications in computational biology and social network analysis, where the goal is to delete a minimum number of ed…
Densest Subhypergraph: Negative Supermodular Functions and Strongly Localized Methods
Yufan Huang, David F. Gleich, Nate Veldt
Dense subgraph discovery is a fundamental primitive in graph and hypergraph analysis which among other applications has been used for real-time story detection on social media and…
Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling
Vedangi Bengali, Nate Veldt
Graph clustering is a fundamental task in network analysis where the goal is to detect sets of nodes that are well-connected to each other but sparsely connected to the rest of the…
On the Optimal Recovery of Graph Signals
Simon Foucart, Chunyang Liao, Nate Veldt
Learning a smooth graph signal from partially observed data is a well-studied task in graph-based machine learning. We consider this task from the perspective of optimal recovery,…
Overlapping and Robust Edge-Colored Clustering in Hypergraphs
Alex Crane, Brian Lavallee, Blair D. Sullivan +1
A recent trend in data mining has explored (hyper)graph clustering algorithms for data with categorical relationship types. Such algorithms have applications in the analysis of soc…
Seven open problems in applied combinatorics
Sinan G. Aksoy, Ryan Bennink, Yuzhou Chen +10
We present and discuss seven different open problems in applied combinatorics. The application areas relevant to this compilation include quantum computing, algorithmic differentia…
Cut-matching Games for Generalized Hypergraph Ratio Cuts
Nate Veldt
Hypergraph clustering is a basic algorithmic primitive for analyzing complex datasets and systems characterized by multiway interactions, such as group email conversations, groups…
Growing a Random Maximal Independent Set Produces a 2-approximate Vertex Cover
Nate Veldt
This paper presents a fast and simple new 2-approximation algorithm for minimum weighted vertex cover. The unweighted version of this algorithm is equivalent to a well-known greedy…
Optimal LP Rounding and Linear-Time Approximation Algorithms for Clustering Edge-Colored Hypergraphs
Nate Veldt
We study the approximability of an existing framework for clustering edge-colored hypergraphs, which is closely related to chromatic correlation clustering and is motivated by mach…
Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds
Nate Veldt
Correlation clustering is a widely studied framework for clustering based on pairwise similarity and dissimilarity scores, but its best approximation algorithms rely on impractical…
Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components
Nate Veldt, Austin R. Benson, Jon Kleinberg
Minimizing a sum of simple submodular functions of limited support is a special case of general submodular function minimization that has seen numerous applications in machine lear…
fauci-email: a json digest of Anthony Fauci's released emails
Austin R. Benson, Nate Veldt, David F. Gleich
A collection of over 3000 pages of emails sent by Anthony Fauci and his staff were released in an effort to understand the United States government response to the COVID-19 pandemi…
The Generalized Mean Densest Subgraph Problem
Nate Veldt, Austin R. Benson, Jon Kleinberg
Finding dense subgraphs of a large graph is a standard problem in graph mining that has been studied extensively both for its theoretical richness and its many practical applicatio…
Combinatorial Characterizations and Impossibilities for Higher-order Homophily
Nate Veldt, Austin R. Benson, Jon Kleinberg
Homophily is the seemingly ubiquitous tendency for people to connect and interact with other individuals who are similar to them. This is a well-documented principle and is fundame…
Generative hypergraph clustering: from blockmodels to modularity
Philip S. Chodrow, Nate Veldt, Austin R. Benson
Hypergraphs are a natural modeling paradigm for a wide range of complex relational systems. A standard analysis task is to identify clusters of closely related or densely interconn…