On Single-Objective Sub-Graph-Based Mutation for Solving the Bi-Objective Minimum Spanning Tree Problem

• URL: http://arxiv.org/abs/2306.00222v1
• Date: Wed, 31 May 2023 22:35:17 GMT
• Title: On Single-Objective Sub-Graph-Based Mutation for Solving the Bi-Objective Minimum Spanning Tree Problem
• Authors: Jakob Bossek, Christian Grimme
• Abstract summary: We contribute to the efficient approximation of the $mathcalNP$-hard multi-objective minimum spanning tree problem (moMST) adopting evolutionary computation. We design several highly biased sub-graph-based mutation operators founded on the gained insights. Our results confirm that the sub-graph based operators beat baseline algorithms from the literature.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We contribute to the efficient approximation of the Pareto-set for the classical $\mathcal{NP}$-hard multi-objective minimum spanning tree problem (moMST) adopting evolutionary computation. More precisely, by building upon preliminary work, we analyse the neighborhood structure of Pareto-optimal spanning trees and design several highly biased sub-graph-based mutation operators founded on the gained insights. In a nutshell, these operators replace (un)connected sub-trees of candidate solutions with locally optimal sub-trees. The latter (biased) step is realized by applying Kruskal's single-objective MST algorithm to a weighted sum scalarization of a sub-graph. We prove runtime complexity results for the introduced operators and investigate the desirable Pareto-beneficial property. This property states that mutants cannot be dominated by their parent. Moreover, we perform an extensive experimental benchmark study to showcase the operator's practical suitability. Our results confirm that the sub-graph based operators beat baseline algorithms from the literature even with severely restricted computational budget in terms of function evaluations on four different classes of complete graphs with different shapes of the Pareto-front.

Related papers

• Ensemble-Based Unsupervised Discontinuous Constituency Parsing by Tree Averaging [25.952659018194293]
  We build an ensemble of different runs of the existing discontinuous parsing constituency. We develop an efficient exact algorithm to tackle the task, which runs in a reasonable time for all samples. Results on three datasets show our method outperforms all baselines in all metrics.
  arXiv  Detail & Related papers  (2024-02-29T21:49:31Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems [16.803653908913514]
  We study the multi-objective minimum weight base problem, an abstraction of classical NP-hard problems such as the multi-objective minimum spanning tree problem. We prove some important properties of the convex hull of the non-dominated front, such as its approximation quality and an upper bound on the number of extreme points. We show that the MOEA/D algorithm, given an appropriate setting, finds all extreme points within expected fixed-objective time in the oracle model.
  arXiv  Detail & Related papers  (2023-06-06T05:13:29Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• On graph-based reentrancy-free semantic parsing [5.228711636020665]
  We propose a graph-based approach for semantic parsing that resolves two problems observed in the literature. We prove that both MAP inference and latent tag anchoring (required for weakly-supervised learning) are NP-hard problems. We propose two optimization algorithms based on constraint smoothing and conditional gradient to approximately solve these inference problems.
  arXiv  Detail & Related papers  (2023-02-15T14:14:09Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  We propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints. The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k) and it outperforms all previous state-of-the-arts on all benchmarks.
  arXiv  Detail & Related papers  (2022-01-05T13:37:27Z)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  We consider the problem of discovering $K related Gaussian acyclic graphs (DAGs) Under multi-task learning setting, we propose a $l_1/l$-regularized maximum likelihood estimator (MLE) for learning $K$ linear structural equation models. We theoretically show that the joint estimator, by leveraging data across related tasks, can achieve a better sample complexity for recovering the causal order.
  arXiv  Detail & Related papers  (2021-11-03T22:10:18Z)
• Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
  We present the sample complexities of Recursive Grouping (RG) and Chow-Liu Recursive Grouping (CLRG) We robustify RG, CLRG, Neighbor Joining (NJ) and Spectral NJ (SNJ) by using the truncated inner product. We derive the first known instance-dependent impossibility result for structure learning of latent trees.
  arXiv  Detail & Related papers  (2021-06-02T01:37:52Z)
• Measure Inducing Classification and Regression Trees for Functional Data [0.0]
  We propose a tree-based algorithm for classification and regression problems in the context of functional data analysis. This is achieved by learning a weighted functional $L2$ space by means of constrained convex optimization.
  arXiv  Detail & Related papers  (2020-10-30T18:49:53Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  We present techniques that produce optimal decision trees over a variety of objectives. We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables.
  arXiv  Detail & Related papers  (2020-06-15T19:00:11Z)

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.