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.
Combines TSP and SC to solve real-world vaccine distribution.
Structure learning of Bayesian networks is an important problem that arises in numerous machine learning applications. In this work, we present a novel approach for learning the structure of Bayesian networks using the solution of an appropriately constructed traveling salesman problem. In our approach, one computes an…
Resolving Schwartz's quadratic meander number conjecture
In this paper a highly abstracted view on the historical development of Genetic Algorithms for the Traveling Salesman Problem is given. In a meta-data analysis three phases in the development can be distinguished. First exponential growth in interest till 1996 can be observed, growth stays linear till 2011 and after th…
We explore the impact of learning paradigms on training deep neural networks for the Travelling Salesman Problem. We design controlled experiments to train supervised learning (SL) and reinforcement learning (RL) models on fixed graph sizes up to 100 nodes, and evaluate them on variable sized graphs up to 500 nodes. Be…
Deep RL learns 2-opt heuristics to improve TSP solutions.
Machine learning reduces combinatorial optimization problem dimensions.
This paper introduces a new learning-based approach for approximately solving the Travelling Salesman Problem on 2D Euclidean graphs. We use deep Graph Convolutional Networks to build efficient TSP graph representations and output tours in a non-autoregressive manner via highly parallelized beam search. Our approach ou…
A new scheme reduces global search cost by a square root factor.
Sym-NCO leverages symmetricities to improve DRL-NCO performance.
Linear-time graph optimization using reinforcement learning.
Equity-Transformer solves NP-hard min-max routing problems efficiently.
Two DRL policies collaborate to solve NP-hard routing problems.
Deep learning has been extended to a number of new domains with critical success, though some traditional orienteering problems such as the Travelling Salesman Problem (TSP) and its variants are not commonly solved using such techniques. Deep neural networks (DNNs) are a potentially promising and under-explored solutio…
DeepCO uses deep learning for offline combinatorial optimization in warehouse operations.
This paper presents a framework to tackle combinatorial optimization problems using neural networks and reinforcement learning. We focus on the traveling salesman problem (TSP) and train a recurrent network that, given a set of city coordinates, predicts a distribution over different city permutations. Using negative t…
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…
In this paper we introduce a new neural architecture for sorting unordered sequences where the correct sequence order is not easily defined but must rather be inferred from training data. We refer to this architecture as OrderNet and describe how it was constructed to be naturally permutation equivariant while still al…
When a black-box optimization objective can only be evaluated with costly or noisy measurements, most standard optimization algorithms are unsuited to find the optimal solution. Specialized algorithms that deal with exactly this situation make use of surrogate models. These models are usually continuous and smooth, whi…
In this work, we provide theoretical guarantees for reward decomposition in deterministic MDPs. Reward decomposition is a special case of Hierarchical Reinforcement Learning, that allows one to learn many policies in parallel and combine them into a composite solution. Our approach builds on mapping this problem into a…
The recently presented idea to learn heuristics for combinatorial optimization problems is promising as it can save costly development. However, to push this idea towards practical implementation, we need better models and better ways of training. We contribute in both directions: we propose a model based on attention …
Bayesian optimization method for permutations accelerates combinatorial search.
In this work, we introduce Graph Pointer Networks (GPNs) trained using reinforcement learning (RL) for tackling the traveling salesman problem (TSP). GPNs build upon Pointer Networks by introducing a graph embedding layer on the input, which captures relationships between nodes. Furthermore, to approximate solutions to…
The design of good heuristics or approximation algorithms for NP-hard combinatorial optimization problems often requires significant specialized knowledge and trial-and-error. Can we automate this challenging, tedious process, and learn the algorithms instead? In many real-world applications, it is typically the case t…
DPDP combines neural heuristics with DP for vehicle routing problems.
New research shows deep learning struggles with hard problems due to biased data generation.
This paper explores the possibility of near-optimally solving multi-agent, multi-task NP-hard planning problems with time-dependent rewards using a learning-based algorithm. In particular, we consider a class of robot/machine scheduling problems called the multi-robot reward collection problem (MRRC). Such MRRC problem…
Adversarial self-play in two-player games has delivered impressive results when used with reinforcement learning algorithms that combine deep neural networks and tree search. Algorithms like AlphaZero and Expert Iteration learn tabula-rasa, producing highly informative training data on the fly. However, the self-play t…
New framework analyzes effectiveness of neural network-based combinatorial problem solvers.
We introduce a new neural architecture to learn the conditional probability of an output sequence with elements that are discrete tokens corresponding to positions in an input sequence. Such problems cannot be trivially addressed by existent approaches such as sequence-to-sequence and Neural Turing Machines, because th…
We introduce the problem of hidden Hamiltonian cycle recovery, where there is an unknown Hamiltonian cycle in an -vertex complete graph that needs to be inferred from noisy edge measurements. The measurements are independent and distributed according to $\calP_n$ for edges in the cycle and $\calQ_n$ otherwise. This …
New L2D framework allows deferring specific parts of a sequence prediction to experts.
Introduces topological deep learning for neural network classification problems.
The goal of Machine Learning to automatically learn from data, extract knowledge and to make decisions without any human intervention. Such automatic (aML) approaches show impressive success. Recent results even demonstrate intriguingly that deep learning applied for automatic classification of skin lesions is on par w…
Optimizes material distribution on surfaces using topological derivatives.
Paper tackles dynamic graph topology identification in time-varying graphs.
Topological obstructions to admissibility in -Loewner--Nirenberg problem
Several rigidity problems in toric topology are addressed in \cite{ma-su08}. In this paper, we survey results on those problems including recent development.
Topology aids in solving machine learning classification problems.
The authors study the Hodge theory of the exterior differential operator acting on -forms on a smoothly bounded domain in $\RR^{N+1}$, and on the half space $\rnp$. The novelty is that the topology used is not an topology but a Sobolev topology. This strikingly alters the problem as compared to the classic…
Paper speeds up topological signal identification and cycle matching.
TDL uses topological features for deep learning models, promising new insights and solutions.
Novel algorithm learns sparse signal representations over topological spaces.
New method for inferring network topology from partial data.
Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies important problems involving both computation and topology.
Detects graph topology changes from noisy signals using prior spectral information.
A groupoid is a small category in which each morphism has an inverse. A topological groupoid is a groupoid in which both sets of objects and morphisms have topologies such that all groupoid structure maps are continuous. The notion of monodromy groupoid of a topological groupoid generalises those of fundamental groupoi…
Survey of mass partition problems in geometry and topology.