Permutation Picture of Graph Combinatorial Optimization Problems

2024/10/22 by Yimeng Min, Min, Yimeng
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Algorithm #Artificial Intelligence (cs.AI) #Combinatorial optimization #Combinatorics #Computer science #FOS: Computer and information sciences #Graph #Machine Learning (cs.LG) #Mathematics #Permutation (music) #Permutation graph #Physics #Theoretical computer science #Vehicle Routing Optimization Methods

paper · pdf · doi:10.48550/arxiv.2410.17111

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2024/10/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper proposes a framework that formulates a wide range of graph combinatorial optimization problems using permutation-based representations. These problems include the travelling salesman problem, maximum independent set, maximum cut, and various other related problems. This work potentially opens up new avenues for algorithm design in neural combinatorial optimization, bridging the gap between discrete and continuous optimization techniques.

Related

• Structure As Search: Unsupervised Permutation Learning for Combinatorial Optimization
• Neural Combinatorial Optimization with Reinforcement Learning
• Neural Combinatorial Optimization: a New Player in the Field
• Are Graph Neural Networks Optimal Approximation Algorithms?
• Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems