Polynomial-time method solves complex combinatorial semi-bandits.
problem Optimal strategies for combinatorial semi-bandits with uncorrelated Gaussian rewards.
method Proposes a polynomial-time method to solve the Graves-Lai optimization problem for various combinatorial structures.
result First known approach to implement asymptotically optimal algorithms in polynomial time for combinatorial semi-bandits.
Combinatorial method computes Legendrian knot invariant.
problem Computing the Heegaard Floer contact invariant for Legendrian knots.
method Combining Plamenevskaya's combinatorial description with Heegaard Floer theory.
result Hat version of LOSS invariant can be computed combinatorially.
Study inert and ambiguous classes in modular group using combinatorial methods.
problem Counting inert and ambiguous conjugacy classes in modular group.
method Purely combinatorial approach using word length in free product representation.
result Exact counting formulas and asymptotic growth rates for inert and ambiguous classes.
MOCA-HESP optimizes high-dimensional combinatorial and mixed spaces using hyper-ellipsoid partitioning.
problem Challenges in optimizing high-dimensional, combinatorial and mixed spaces.
method MOCA-HESP uses hyper-ellipsoid space partitioning with different categorical encoders and multi-armed bandit for adaptive selection.
result MOCA-HESP outperforms existing methods on various synthetic and real-world benchmarks.
Sarkar and Wang have given a combinatorial algorithm for computing Heegaard Floer homology and Plamenevskaya has improved their method to compute Ozsvath-Szabo invariant. In this paper, applying the combinatorial method to stabilizations of an open book, we prove basic properties of Ozsvath-Szabo invariant.
Proves a formula in Heegaard Floer homology using combinatorial methods.
problem Proving Lipshitz's Maslov index formula in Heegaard Floer homology.
method Combinatorial proof via Heegaard diagrams.
result Validated Lipshitz's Maslov index formula in Heegaard Floer homology.
Bayesian optimization method tackles combinatorial spaces, scalable for large data.
problem Optimization over combinatorial categorical spaces in natural sciences.
method Combines variational optimization and continuous relaxations for gradient-based optimization.
result Method performs comparably to state-of-the-art methods while scaling well.
New combinatorial method for sparse PCA works beyond spiked identity model.
problem Sparse PCA under general covariance matrices.
method Combinatorial truncated power method with global convergence guarantee.
result First combinatorial sparse PCA method provably successful for general covariance matrices.
Bayesian optimization adapted for discrete spaces using random mappings.
problem Global optimization of expensive black-box functions with discrete variables.
method Embeds discrete space into a convex polytope, performs optimization in continuous space.
result Method outperforms existing methods in large combinatorial spaces.
A new method uses heat diffusion to efficiently solve combinatorial optimization problems.
problem Challenges in combinatorial optimization due to discrete nature and limited search scope.
method Transforming the target function through heat diffusion to enable information flow and more efficient navigation.
result Superior performance across various combinatorial optimization problems.
LGS-Net improves NCO performance on combinatorial optimization tasks.
problem NP-hard combinatorial optimization problems in logistics, manufacturing, and drug discovery.
method LGS-Net uses a latent space model that conditions on problem instances and introduces Latent Guided Sampling for efficient inference.
result Empirical results show state-of-the-art performance on benchmark routing tasks.
New method finds ideal circle patterns on spheres.
problem Finding ideal circle patterns on spheres with prescribed curvatures.
method Combinatorial Calabi flow in spherical geometry.
result Existence and convergence of the flow for ideal circle patterns.
Bayesian optimization method for permutations accelerates combinatorial search.
problem Optimizing expensive-to-evaluate objectives on permutation problems.
method LAW2ORDER, a batch Bayesian optimization method based on the acquisition weighted kernel.
result LAW2ORDER achieves sublinear batch cumulative regret, demonstrating accelerated search.
The paper extends log-Sobolev inequalities to matrix-valued settings using combinatorial methods.
problem Log-Sobolev inequalities for matrix-valued settings.
method Combining noncommutative geometry tools and combinatorial methods.
result Combinatorial methods yield computable lower bounds for matrix-valued log-Sobolev inequalities.
New method uses diffusion models for unsupervised combinatorial optimization.
problem Learning to sample from intractable discrete distributions without training data.
method Lifts the restriction of generative models needing exact sample likelihoods using a loss that bounds reverse KL divergence.
result Achieves new state-of-the-art results in data-free Combinatorial Optimization.
New method finds metrics on surfaces with prescribed curvatures using circle packings and surgery.
problem Finding piecewise Euclidean metrics on surfaces with prescribed combinatorial curvatures.
method Combinatorial curvature flows with surgery for inversive distance circle packings.
result Longtime existence and global convergence of combinatorial curvature flows with surgery.
DeepCO uses deep learning for offline combinatorial optimization in warehouse operations.
problem Optimizing warehouse operation sequences in offline settings.
method DeepCO framework utilizing distribution regularized optimization for TSP.
result DeepCO reduces route length by 5.7% on average for TSP problems.
Study infinite combinatorial Ricci flow on spherical surfaces.
problem Investigate infinite combinatorial Ricci flow with spherical background.
method Establish existence and convergence of solution for infinite cellular decompositions.
result Existence and convergence of solution for infinite combinatorial Ricci flow in spherical geometry.
The optimization of expensive-to-evaluate black-box functions over combinatorial structures is an ubiquitous task in machine learning, engineering and the natural sciences. The combinatorial explosion of the search space and costly evaluations pose challenges for current techniques in discrete optimization and machine …
Defines annulus complex of handlebodies and proves its connectivity.
problem None explicitly stated; focus on definition and proof.
method Combinatorial methods to prove connectivity.
result Connectivity of annulus complex of handlebodies proven.
Combines combinatorial method to extend Milnor invariants to welded links.
problem Extending Milnor invariants to welded links.
method Combinatorial approach.
result Invariance of extended Milnor invariants for welded links.
New algorithm eliminates arms to minimize regret in complex bandit problems.
problem Minimizing regret in combinatorial bandit problems with explicit exploration.
method Introduces a novel arm elimination scheme that partitions arms into three categories and incorporates explicit exploration.
result Achieves near-optimal regret in combinatorial multi-armed and linear contextual bandit problems.
VCSMC improves efficiency in Bayesian phylogenetic inference.
problem Inefficient exploration of phylogenetic state space.
method Variational Combinatorial Sequential Monte Carlo (VCSMC) and nested CSMC.
result VCSMC and VNCSMC explore higher probability spaces efficiently.
Graph neural networks improve combinatorial optimization by leveraging inductive bias.
problem Combinatorial optimization problems often arise from related data distributions.
method Using graph neural networks to enhance or solve combinatorial tasks.
result Graph neural networks effectively encode combinatorial and relational input.
A framework for generating 3D shapes by sequentially assembling primitives.
problem Combinatorial complexity in generating 3D shapes.
method Bayesian optimization for efficient exploration and exploitation of feasible combinations.
result Successfully generates realistic combinatorial 3D shapes.
This work proposes an unsupervised neural network framework for solving combinatorial optimization problems on graphs.
problem Challenges in neural networks solving combinatorial optimization problems without labeled instances.
method Inspired by Erdos' probabilistic method, a neural network parametrizes a probability distribution over sets, optimizing it to find low-cost integral solutions.
result The method provides valid solutions to the maximum clique problem and local graph clustering, achieving competitive results.
Generalizes cohomology ring result for combinatorial line arrangements.
problem Cohomology ring of boundary manifold for combinatorial line arrangements.
method Introduced boundary manifold, constructed homology cycles, computed cohomology ring.
result Cohomology ring of boundary manifold is isomorphic to double of Orlik-Solomon algebra.
New active learning method uses combinatorial coverage to improve data transfer and reduce bias.
problem Inability to transfer sampled data to new models and sampling bias issues.
method Data-centric active learning methods utilizing combinatorial coverage.
result Sampling data with coverage leads to better data transfer and competitive sampling bias.
We describe a new method for combinatorially computing the transverse invariant in knot Floer homology. Previous work of the authors and Stone used braid diagrams to combinatorially compute knot Floer homology of braid closures. However, that approach was unable to explicitly identify the invariant of transverse links …
New method improves combinatorial optimization by overcoming inefficient sampling.
problem Wandering in contours: sampling similar solutions for long periods.
method Reheated Gradient-based Discrete Sampling with a novel mechanism.
result Superior performance across various combinatorial optimization problems.
New method improves combinatorial optimization by capturing dependencies among solution variables.
problem Performance limitations in solving combinatorial optimization problems using independent solution variables.
method Subgraph tokenization and variational annealing to capture dependencies and improve learning efficiency.
result Empirical evidence shows superior performance of autoregressive methods with tokenization and annealed entropy regularization.
New framework analyzes effectiveness of neural network-based combinatorial problem solvers.
problem Analyzing neural network-based methods for combinatorial optimization problems.
method Introducing a theoretical framework to assess the effectiveness of solution-samplers using policy-gradient methods.
result Positive theoretical answer to the existence of expressive, tractable, and benign optimization landscapes for combinatorial problems.
In this paper, we introduce a new combinatorial curvature on two and three dimensional triangulated manifolds, which transforms in the same way as that of the smooth scalar curvature under scaling of the metric and could be used to approximate the Gauss curvature on two dimensional manifolds. Then we use the flow metho…
ML4CO uses machine learning to improve combinatorial optimization solvers.
problem Solving combinatorial problems in practice often involves related data distributions.
method Replacing heuristic components with machine learning approaches.
result Improved state-of-the-art combinatorial optimization solvers.
RL improves combinatorial optimization by automating heuristic search.
problem Hard combinatorial optimization problems with suboptimal solutions.
method Training RL agents to solve these problems.
result RL can outperform traditional algorithms in solving complex problems.
Novel theory combines combinatorial and topological elements.
problem Understanding combinatorial phenomena at the intersection of topology.
method Synthesizes combinatorial and topological approaches with a new framing concept.
result Framed combinatorial spaces exhibit better behavior than classical spaces.
Achieving fusion of deep learning with combinatorial algorithms promises transformative changes to artificial intelligence. One possible approach is to introduce combinatorial building blocks into neural networks. Such end-to-end architectures have the potential to tackle combinatorial problems on raw input data such a…
Algorithm constructs and classifies weaving diagrams using combinatorial methods.
problem Classifying unique weaving diagrams with over/under information.
method Systematic algorithm based on tiling and crossing matrices.
result Classification of periodic structures based on minimum crossings.
Bayesian optimization for high-dimensional combinatorial spaces using embeddings.
problem Optimizing expensive functions over large, complex input spaces.
method Dictionary-based ordinal embeddings for high-dimensional combinatorial structures, using Gaussian process models.
result The proposed method outperforms state-of-the-art BO methods on diverse real-world benchmarks.
The paper introduces combinatorial Calabi flows to find hyperbolic metrics on surfaces with boundary.
problem Finding hyperbolic metrics on surfaces with totally geodesic boundaries of given lengths.
method Introducing combinatorial Calabi flows and proving their long time existence and global convergence.
result Proves the long time existence and global convergence of combinatorial Calabi flow on surfaces with boundary.
We propose a new family of combinatorial inference problems for graphical models. Unlike classical statistical inference where the main interest is point estimation or parameter testing, combinatorial inference aims at testing the global structure of the underlying graph. Examples include testing the graph connectivity…
The paper shows how sublinearly Morse boundaries can be understood through combinatorial methods.
problem Understanding sublinearly Morse boundaries in cubulated groups and CAT(0) cube complexes.
method Combining geometric and combinatorial approaches to analyze sublinearly Morse boundaries.
result Sublinearly Morse boundaries can be described combinatorially and continuously related to Gromov and Roller boundaries.
Oracle-efficient algorithms reduce combinatorial semi-bandit regret to logarithmic time.
problem Scalability issue in combinatorial semi-bandit problems due to high combinatorial optimization costs.
method Oracle-efficient frameworks that minimize oracle queries while maintaining tight regret guarantees.
result Achieved i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) regret with O ( log log T ) O(\log\log T) O ( log log T ) oracle queries for worst-case linear rewards. The paper develops algorithms for finding metrics with prescribed combinatorial curvature on polyhedral surfaces.
problem Finding metrics with prescribed combinatorial curvature on polyhedral surfaces.
method Discrete uniformization theorem, combinatorial α-Yamabe flow, combinatorial α-Calabi flow, edge flipping surgery.
result Longtime existence and convergence of combinatorial α-Yamabe flow and combinatorial α-Calabi flow with surgery.
This paper focuses on Bayesian Optimization (BO) for objectives on combinatorial search spaces, including ordinal and categorical variables. Despite the abundance of potential applications of Combinatorial BO, including chipset configuration search and neural architecture search, only a handful of methods have been pro…
The paper introduces combinatorial curvature and flow for polyhedral surfaces, proving rigidity and solving the Yamabe problem.
problem Discrete conformal structures on polyhedral surfaces and their rigidity.
method Parameterized combinatorial curvature, combinatorial α-Ricci flow, and flow extension through singularities.
result Existence and convergence of combinatorial α-Ricci flow for solving the Yamabe problem.
The purpose of this thesis is to study classical combinatorial objects, such as polytopes, polytopal complexes, and subspace arrangements, using tools that have been developed in combinatorial topology, especially those tools developed in connection with (discrete) differential geometry, geometric group theory and low-…
A method learns to solve multilevel combinatorial problems with two players.
problem Multilevel combinatorial optimization problems with multiple players.
method Value-based multi-agent reinforcement learning in a graph neural network framework.
result Close to optimal solutions on graphs up to 100 nodes, with a significant speedup.