arXiv research

Differentiable cutting-plane layers solve parametric mixed-integer linear optimization problems.

Paper connects probability density cuts to graph theory eigenfunctions.

New equivalence relation for links using cut-diagrams.

Proves a generalized Whitehead cut vertex lemma for tree groups.

Unified framework for differentiable graph partitioning with probabilistic cuts.

A symplectic cut of a manifold M with a Hamiltonian circle action is a symplectic quotient of M x C. If M is Kaehler then, since C is Kaehler, the cut space is Kaehler as well. The symplectic structure on the cut is well understood. In this paper we describe the complex structure (and hence the metric) on the cut. We t…

Study shows convergence rates for Cheeger cuts on data clouds.

Generalizes neural network verification by adding arbitrary cutting planes.

Extends Milnor invariants to surface-links using cut-diagrams.

In this note, we study the cut locus of the free, step two Carnot groups $\mathbb{G}_k$ with $k$ generators, equipped with their left-invariant Carnot-Carathéodory metric. In particular, we disprove the conjectures on the shape of the cut loci proposed in [Myasnichenko - 2002] and [Montanari, Morbidelli - 2016], by exh…

We showed in another paper [arXiv:1103.1759] that every connected graph can be realized as the cut locus of some point on some riemannian surface $S$. Here, criteria for the orientability of $S$ are given, and are applied to classify the distinct, orientable, cut locus structures on graphs with four generating cycles.

Study shows zero probability of cut locus for Fréchet mean on Riemannian manifolds.

NeuralCut learns to select cutting planes by looking ahead, outperforming traditional methods.

NeVI-Cut uses neural networks to efficiently propagate uncertainty without feedback.

We propose a new method to model multi-way similarities into hypergraphs for clustering.

Study Riemannian metrics on lens spaces, find cut loci and diameters.

Study Riemannian metrics on lens spaces, find cut loci and diameters.

We consider a left invariant Riemannian metric on SO(3) with two equal eigenvalues. We find the cut locus and the equation for the cut time. We find the diameter of such metric and describe the set of all most distant points from the identity. Also we prove that the cut locus and the cut time converge to the cut locus …

Integer programming (IP) is a general optimization framework widely applicable to a variety of unstructured and structured problems arising in, e.g., scheduling, production planning, and graph optimization. As IP models many provably hard to solve problems, modern IP solvers rely on many heuristics. These heuristics ar…

Stability of cut locus under metric perturbations in compact Riemannian manifolds.

Study on cut locus of submanifolds in Finsler geometry.

In the paper we consider the Stiefel manifold $V_{n;k}$ as a principal $U(k)$- bundle over the Grassmann manifold and study the cut locus from the unit element. We gave the complete description of this cut locus on $V_{n;1}$ and presented the sufficient condition on the general case. At the end, we study the complement…

We consider the nilpotent left-invariant sub-Riemannian structure on the Engel group. This structure gives a fundamental local approximation of a generic rank 2 sub-Riemannian structure on a 4-manifold near a generic point (in particular, of the kinematic models of a car with a trailer). On the other hand, this is the …

We present and analyze a central cutting surface algorithm for general semi-infinite convex optimization problems, and use it to develop a novel algorithm for distributionally robust optimization problems in which the uncertainty set consists of probability distributions with given bounds on their moments. Moments of a…

Generalizes results for Riemannian manifolds with boundary to those without.

We discuss a general framework for cutting constructions and reinterpret in this setting the work on non-Abelian symplectic cuts by Weitsman. We then introduce two analogous non-Abelian modification constructions for hyperkähler manifolds: one modifies the topology significantly, the other gives metric deformations. We…

New Karger-like algorithms solve graph cuts, useful for image segmentation.

The study defines new surfaces with specific cut locus properties and provides conditions for their existence.

Extends Penrose's method to null shells with pressure and energy flux.

A local cut point is by definition a point that disconnectes its sufficiently small neighborhood. We show that there exists an upper bound for the degree of a local cut point in a metric measure space satisfying the generalized Bishop--Gromov inequality. As a corollary, we obtain an upper bound for the number of ends o…

Stochastic cutting planes improve data-driven optimization speed.

Multisections generalize trisections for 4-manifolds, allowing complex operations and explicit diagrams.

Study of Randers metrics on spheres with simple cut loci.

We prove that every connected graph can be realized as the cut locus of some point on some Riemannian surface $S$ which, in some cases, has constant curvature. We study the stability of such realizations, and their generic behavior.

Reduced sub-Riemannian time on a specific group structure.

Algorithms based on spectral graph cut objectives such as normalized cuts, ratio cuts and ratio association have become popular in recent years because they are widely applicable and simple to implement via standard eigenvector computations. Despite strong performance for a number of clustering tasks, spectral graph cu…

In the present paper we study the structure of the cut locus of a Randers rotational 2-sphere of revolution $(M, F = α+β)$. We show that in the case when the Gaussian curvature of the Randers surface is monotone along a meridian, the cut locus of a point $q\in M$ is a point on a subarc of the opposite half bending meri…

We define spin-c prequantization of a symplectic manifold to be a spin-c structure and a connection which are compatible with the symplectic form. We describe the cutting of an S^1-equivariant spin-c prequantization. The cutting process involves a choice of a spin-c prequantization for the complex plane. We prove that …

We show that some riemannian manifolds diffeomorphic to the sphere have the property that the cut loci of general points are smoothly embedded closed disks of codimension one. Ellipsoids with distinct axes are typical examples of such manifolds.

Max flow/min cut theorem extended to currents and topology.

Spectral Clustering as a relaxation of the normalized/ratio cut has become one of the standard graph-based clustering methods. Existing methods for the computation of multiple clusters, corresponding to a balanced $k$-cut of the graph, are either based on greedy techniques or heuristics which have weak connection to th…

Spectral clustering is sensitive to how graphs are constructed from data particularly when proximal and imbalanced clusters are present. We show that Ratio-Cut (RCut) or normalized cut (NCut) objectives are not tailored to imbalanced data since they tend to emphasize cut sizes over cut values. We propose a graph partit…

Nilpotent groups can't be biLipschitz embedded into $L^1$.

This paper establishes the consistency of a family of graph-cut-based algorithms for clustering of data clouds. We consider point clouds obtained as samples of a ground-truth measure. We investigate approaches to clustering based on minimizing objective functionals defined on proximity graphs of the given sample. Our f…

New upper bound for geodesic complexity derived from cut locus decompositions.

Min-cut clustering, based on minimizing one of two heuristic cost-functions proposed by Shi and Malik, has spawned tremendous research, both analytic and algorithmic, in the graph partitioning and image segmentation communities over the last decade. It is however unclear if these heuristics can be derived from a more g…

This work reviews left-invariant optimal control problems on Lie groups.

New 2-spheres of revolution with simple cut locus structures.