We give a combinatorial characterization of generic minimal rigidity for planar periodic frameworks. The characterization is a true analogue of the Maxwell-Laman Theorem from rigidity theory: it is stated in terms of a finite combinatorial object and the conditions are checkable by polynomial time combinatorial algorit…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “combinatorial framework”
Unified framework for combinatorial and rounding algorithms in experimental design.
problem Designing and analyzing combinatorial and rounding algorithms for experimental design problems.
method Local search framework for combinatorial algorithms and regret minimization framework for rounding algorithms.
result Unified approach to match and improve all known results in D/A/E-design and obtain new results in unknown settings.
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.
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.
Unified framework for gradient estimation in combinatorial spaces.
problem Scaling relaxed gradient estimators to large combinatorial distributions.
method Introducing stochastic softmax tricks within the perturbation model framework.
result Stochastic softmax tricks improve model performance and discover more latent structure.
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.
We extend our generic rigidity theory for periodic frameworks in the plane to frameworks with a broader class of crystallographic symmetry. Along the way we introduce a new class of combinatorial matroids and associated linear representation results that may be interesting in their own right. The same techniques immedi…
Neural Learning of One-of-Many Solutions for Combinatorial Problems in Structured Output Spacescs.LG
Neural framework learns one solution from multiple for combinatorial problems.
problem Finding any one of many possible solutions for combinatorial problems.
method Adapts existing prediction networks to handle solution multiplicity using a selection module trained via RL.
result Framework significantly improves accuracy in solving combinatorial problems.
Paper tackles combinatorial reinforcement learning with preference feedback.
problem Modeling long-term user engagement in scenarios like recommender systems and online advertising.
method Assumes a contextual MNL preference model with linear mean utilities and approximates item values. Proposes MNL-VQL algorithm.
result Achieves nearly minimax-optimal regret for linear MDPs with preference feedback.
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.
Develops a combinatorial semi-bandit method for electric vehicle charging station selection.
problem Long-distance navigation for BEVs with unknown charging station availability and performance.
method Combinatorial semi-bandit framework, pre-processing road network, Bayesian modeling, Thompson Sampling, BayesUCB, Epsilon-greedy.
result Demonstrates improved navigation performance on long-distance BEV charging station selection.
New framework for resilient bi-criteria optimization under noisy feedback.
problem Bi-criteria combinatorial optimization with noisy function evaluations.
method Introducing -resilience and developing a black-box framework.
result Achieves sublinear regret and constraint violation for bi-criteria bandit problems.
We study the fundamental properties of curvature in groupoids within the framework of synthetic differential geometry. As is usual in synthetic differential geometry, its combinatorial nature is emphasized. In particular, the classical Bianchi identity is deduced from its combinatorial one.
Theory of symmetric rigidity in hyperbolic geometry.
problem Symmetric rigidity in hyperbolic frameworks.
method Gain graphs and orbit rigidity matrix, matroidal sparsity conditions.
result Characterization of infinitesimal rigidity for Gamma-symmetric frameworks.
A new deep learning framework for topological data.
problem Developing models for data on complex topological domains.
method Introducing combinatorial complexes and developing attention-based CCNNs.
result CCNNs outperform existing models in tasks involving mesh shape analysis and graph learning.
In sponsored search, keyword recommendations help advertisers to achieve much better performance within limited budget. Many works have been done to mine numerous candidate keywords from search logs or landing pages. However, the strategy to select from given candidates remains to be improved. The existing relevance-ba…
We extend to a scheme-theoretic context the notion of a combinatorial differential form, due to A.Kock in the framework of synthetic differential geometry. We show that group-valued combinatorial forms on a scheme may be identified, under very general hypotheses, with traditional Lie algebra-valued differential forms, …
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.
New framework tackles submodular welfare with multi-agent combinatorial bandits.
problem Maximizing total welfare among agents with shared constraints and submodular utilities under bandit feedback.
method Proposes an explore-then-commit strategy with randomized assignments for multi-agent combinatorial bandits.
result Achieves regret, first for partition-based submodular welfare problem under bandit feedback.
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.
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 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.
Study representation varieties of twisted Hopf links using combinatorial and Hodge theory.
problem Representation theory of Hopf link complements with n twists.
method Combinatorial problem and equivariant Hodge theory.
result Close formulas for E-polynomials of representation and character varieties for ranks 2 and 3.
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 regret with oracle queries for worst-case linear rewards.
Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methodscs.LG
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.
There has been an increased interest in discovering heuristics for combinatorial problems on graphs through machine learning. While existing techniques have primarily focused on obtaining high-quality solutions, scalability to billion-sized graphs has not been adequately addressed. In addition, the impact of budget-con…
Paper uses RL to solve constrained combinatorial optimization problems.
problem Constrained combinatorial optimization problems.
method Extending NCO theory to CMDPs, using RL with penalty signals.
result Proposes a superior method for solving constrained problems.
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.
Modular meta-learning is a new framework that generalizes to unseen datasets by combining a small set of neural modules in different ways. In this work we propose abstract graph networks: using graphs as abstractions of a system's subparts without a fixed assignment of nodes to system subparts, for which we would need …
RLD improves combinatorial optimization by avoiding local minima.
problem Efficiently solving combinatorial optimization problems.
method Regularized Langevin Dynamics (RLD) for combinatorial optimization.
result RLD achieves comparable or better performance than previous methods.
Bayesian Optimization for graph node subset functions.
problem Optimizing functions over node subsets in graphs.
method Bayesian Optimization framework for combinatorial optimization on graphs.
result Effectiveness of the proposed BO framework on various graph types and tasks.
Federated learning for combinatorial multi-agent bandits reduces regret and speeds up with fewer communications.
problem Online combinatorial optimization with noisy feedback and cooperation.
method Transforms offline algorithms into online multi-agent algorithms with sublinear regret and communication efficiency.
result Achieves sublinear regret and linear speedup with more agents, communication-efficient.
CRB tackles rising rewards in combinatorial online learning.
problem Rising rewards in combinatorial online learning.
method CRB framework and CRUCB algorithm.
result Empirical and theoretical validation of CRUCB's effectiveness.
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.
A combinatorial framework classifies genus-one knots and links.
problem Classifying knots and links on a torus.
method Maps on surfaces, permutation pairs, bit data, Reidemeister II reductions, state sums.
result Completely enumerated and reproducible genus-one knot and link diagrams.
New GFlowNet training framework using policy gradients for combinatorial object generation.
problem Training efficiency and robustness in GFlowNet models.
method Policy-dependent rewards and coupled training strategy for forward and backward policies.
result Advanced RL perspectives for robust gradient estimation improve GFlowNet performance.
This paper surveys RL for combinatorial optimization, focusing on TSP.
problem Optimizing solutions for combinatorial optimization problems.
method Reinforcement learning applied to combinatorial optimization problems, specifically the TSP.
result Deep learning mechanisms enhance RL algorithms for near-optimal solutions.
A framework for reinforcement learning tackles CVRP with competitive results.
problem Optimizing routes for vehicles with limited capacity.
method Formulates action selection as a mixed-integer optimization problem, uses policy iteration to improve policies.
result Achieves an average gap of 1.7% with state-of-the-art OR methods on CVRP instances.
We propose a new framework for designing estimators for off-policy evaluation in contextual bandits. Our approach is based on the asymptotically optimal doubly robust estimator, but we shrink the importance weights to minimize a bound on the mean squared error, which results in a better bias-variance tradeoff in finite…
This paper extends combinatorial semi-bandits to graph feedback, improving regret bounds.
problem Adversarial combinatorial semi-bandits with graph feedback.
method Introduced graph feedback in combinatorial semi-bandits, using convexified actions and online stochastic mirror descent.
result Optimal regret scales as , interpolating between full and semi-bandit feedback.
We give a combinatorial characterization of generic minimally rigid reflection frameworks. The main new idea is to study a pair of direction networks on the same graph such that one admits faithful realizations and the other has only collapsed realizations. In terms of infinitesimal rigidity, realizations of the former…
The paper surveys some new results and open problems connected with such fundamental combinatorial concepts as polytopes, simplicial complexes, cubical complexes, and subspace arrangements. Particular attention is paid to the case of simplicial and cubical subdivisions of manifolds and, especially, spheres. We describe…
We review some recent results in the generic rigidity theory of planar frameworks with forced symmetry, giving a uniform treatment to the topic. We also give new combinatorial characterizations of minimally rigid periodic frameworks with fixed-area fundamental domain and fixed-angle fundamental domain.
Formula derived for a magnetic line invariant.
problem Solving MHD problems with two-scale mean fields.
method Combinatorial definition of invariant for three-component links.
result Proven formula for invariant verified for simple cases.
Study optimal arms in combinatorial bandits with semi-bandit feedback and finite budget.
problem Finding optimal arms in combinatorial bandits with semi-bandit feedback and finite budget constraints.
method Proposes a generic algorithm covering various arm elimination strategies and derives lower bounds.
result Demonstrates sufficient and necessary budget requirements for finding the best arm.
Unified framework for geometric computation of minimum-area homotopy.
problem Computing the minimum homotopy area of a closed curve.
method Unified combinatorial word approach combining geometric and algebraic methods.
result Unified geometric proof and constructive algorithm for minimum area homotopy.
New combinatorial framework for geometric realizations of subword complexes.
problem Proving or disproving geometric realizations of subword complexes of Coxeter groups.
method Algebraic combinatorics and discrete geometry framework, parameter matrices.
result Existence of parameter matrices equivalent to realizability of subword complexes as chirotopes.
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.