Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking

• URL: http://arxiv.org/abs/2005.11081v2
• Date: Mon, 13 Jul 2020 18:03:39 GMT
• Title: Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking
• Authors: Natalia Vesselinova, Rebecca Steinert, Daniel F. Perez-Ramirez, and Magnus Boman
• Abstract summary: Existing approaches to solving optimization problems on graphs suffer from the need to engineer each problem algorithmically. We organize and compare the structures involved with learning to solve optimization problems, with a special eye on the telecommunications domain.
• Score: 2.817395666721831
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Existing approaches to solving combinatorial optimization problems on graphs suffer from the need to engineer each problem algorithmically, with practical problems recurring in many instances. The practical side of theoretical computer science, such as computational complexity, then needs to be addressed. Relevant developments in machine learning research on graphs are surveyed for this purpose. We organize and compare the structures involved with learning to solve combinatorial optimization problems, with a special eye on the telecommunications domain and its continuous development of live and research networks.

Related papers

• Contractual Reinforcement Learning: Pulling Arms with Invisible Hands [68.77645200579181]
  We propose a theoretical framework for aligning economic interests of different stakeholders in the online learning problems through contract design. For the planning problem, we design an efficient dynamic programming algorithm to determine the optimal contracts against the far-sighted agent. For the learning problem, we introduce a generic design of no-regret learning algorithms to untangle the challenges from robust design of contracts to the balance of exploration and exploitation.
  arXiv  Detail & Related papers  (2024-07-01T16:53:00Z)
• Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective [6.199818486385127]
  We use the trial-and-error paradigm of Reinforcement Learning for discovering better decision-making strategies. This work focuses on non-canonical graph problems for which performant algorithms are typically not known.
  arXiv  Detail & Related papers  (2024-04-09T17:45:25Z)
• On a class of geodesically convex optimization problems solved via Euclidean MM methods [50.428784381385164]
  We show how a difference of Euclidean convexization functions can be written as a difference of different types of problems in statistics and machine learning. Ultimately, we helps the broader broader the broader the broader the broader the work.
  arXiv  Detail & Related papers  (2022-06-22T23:57:40Z)
• Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
  This paper presents a critical analysis on the incorporation of algorithms based on neural networks into the classical optimization framework. A comprehensive study is carried out to analyse the fundamental aspects of such algorithms, including performance, transferability, computational cost and to larger-sized instances.
  arXiv  Detail & Related papers  (2022-05-03T07:54:56Z)
• A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networks [20.170140039052455]
  We propose a radically different approach in that no data is required for training the neural networks that produce the solution. In particular, we reduce the optimization problem to a neural network and employ a dataless training scheme to refine the parameters of the network such that those parameters yield the structure of interest.
  arXiv  Detail & Related papers  (2022-03-15T19:21:31Z)
• Solving Dynamic Graph Problems with Multi-Attention Deep Reinforcement Learning [1.3534683694551497]
  In recent years, using deep learning techniques to find solutions for NP-hard graph problems has gained much interest. In this paper, we propose a novel architecture named Graph Temporal Attention with Reinforcement Learning (GTA-RL) to learn solutions for graph-based dynamic optimization problems.
  arXiv  Detail & Related papers  (2022-01-13T11:36:05Z)
• A Field Guide to Federated Optimization [161.3779046812383]
  Federated learning and analytics are a distributed approach for collaboratively learning models (or statistics) from decentralized data. This paper provides recommendations and guidelines on formulating, designing, evaluating and analyzing federated optimization algorithms.
  arXiv  Detail & Related papers  (2021-07-14T18:09:08Z)
• End-to-End Constrained Optimization Learning: A Survey [69.22203885491534]
  It focuses on surveying the work on integrating solvers and optimization methods with machine learning architectures. These approaches hold the promise to develop new hybrid machine learning and optimization methods to predict fast, approximate, structural, solutions to problems and to enable logical inference.
  arXiv  Detail & Related papers  (2021-03-30T14:19:30Z)
• Combinatorial optimization and reasoning with graph neural networks [7.8107109904672365]
  Combinatorial optimization is a well-established area in operations research and computer science. Recent years have seen a surge of interest in using machine learning, especially graph neural networks (GNNs) as a key building block for tasks.
  arXiv  Detail & Related papers  (2021-02-18T18:47:20Z)
• Graph signal processing for machine learning: A review and new perspectives [57.285378618394624]
  We review a few important contributions made by GSP concepts and tools, such as graph filters and transforms, to the development of novel machine learning algorithms. We discuss exploiting data structure and relational priors, improving data and computational efficiency, and enhancing model interpretability. We provide new perspectives on future development of GSP techniques that may serve as a bridge between applied mathematics and signal processing on one side, and machine learning and network science on the other.
  arXiv  Detail & Related papers  (2020-07-31T13:21:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.