Goto

Collaborating Authors

 mis










Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search

Neural Information Processing Systems

We present a learning-based approach to computing solutions for certain NPhard problems. Our approach combines deep learning techniques with useful algorithmic elements from classic heuristics. The central component is a graph convolutional network that is trained to estimate the likelihood, for each vertex in a graph, of whether this vertex is part of the optimal solution.


Supplement: NN-Baker: A Neural-network Infused Algorithmic Framework for Optimization Problems on Geometric Intersection Graphs Evan McCarty

Neural Information Processing Systems

This condition can be removed by slightly more careful analysis. In what follows, we will show that the output of Baker's paradigm, (d 1) Note that in (Step 2) of Baker's paradigm, after computing We now consider the upper-bound in the bi-criteria approximation. We include the details here for completeness. As seen in Theorem 2.2, the price to pay to obtain By Theorem 3.1 stated in the main text, we can obtain a neural network Following the same argument as in the proof of Theorem 2.1, we know that the resulting This completes the proof of Theorem 3.2. All baselines and NN-Baker models are trained and test on an AMD-EPYC-7452 CPU and a RTX-A6000 GPU.