Empirical Analysis Of Heuristic and Approximation Algorithms for the The Mutual-Visibility Problem

• URL: http://arxiv.org/abs/2507.01076v2
• Date: Tue, 08 Jul 2025 13:11:57 GMT
• Title: Empirical Analysis Of Heuristic and Approximation Algorithms for the The Mutual-Visibility Problem
• Authors: Vanja Stojanović, Bor Pangeršič,
• Abstract summary: This paper implements and evaluating three distinct algorithms -- a direct random behaviour, a hypergraph-based approximation, and a genetic algorithm.<n>Our results demonstrate that for smaller graphs, the algorithms consistently achieve MV set sizes aligning with theoretical bounds.<n> validation on known optimal graphs showed the Genetic Algorithm and other algorithms performing best among tested methods.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The NP-complete mutual-visibility (MV) problem currently lacks empirical analysis on its practical behaviour despite theoretical studies. This paper addresses this gap by implementing and evaluating three distinct algorithms -- a direct random heuristic, a hypergraph-based approximation, and a genetic algorithm -- on diverse synthetic graph datasets, including those with analytically known $\mu(G)$ values and general graph models. Our results demonstrate that for smaller graphs, the algorithms consistently achieve MV set sizes aligning with theoretical bounds. However, for larger instances, achieved solution sizes notably diverge from theoretical limits; this, combined with the absence of tight bounds, complicates absolute quality assessment. Nevertheless, validation on known optimal graphs showed the Genetic Algorithm and other heuristics empirically performing best among tested methods.

Related papers

• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  The proposed method introduces a Quantum Genetic Algorithm (QGA) using a Grover-based evolutionary framework and divide-and-conquer principles.<n>On complete graphs, the proposed method consistently achieves the true optimal MaxCut values, outperforming the Semidefinite Programming (SDP) approach.<n>On ErdHos-R'enyi random graphs, the QGA demonstrates competitive performance, achieving median solutions within 92-96% of the SDP results.
  arXiv  Detail & Related papers  (2025-01-02T05:06:16Z)
• Recombination vs Stochasticity: A Comparative Study on the Maximum Clique Problem [0.393259574660092]
  The maximum clique problem (MCP) is a fundamental problem in graph theory and computational complexity. Various meta-heuristics have been used to approximate the MCP, including genetic and memetic algorithms, ant colony algorithms, greedy algorithms, Tabu algorithms, and simulated annealing. Our results indicate that Monte Carlo algorithms, which employ random searches to generate subgraphs, often surpass genetic algorithms in both speed and capability.
  arXiv  Detail & Related papers  (2024-09-26T12:50:00Z)
• Unlock the Power of Algorithm Features: A Generalization Analysis for Algorithm Selection [25.29451529910051]
  We propose the first provable guarantee for algorithm selection based on algorithm features. We analyze the benefits and costs associated with algorithm features and investigate how the generalization error is affected by different factors.
  arXiv  Detail & Related papers  (2024-05-18T17:38:25Z)
• On the Finite-Time Performance of the Knowledge Gradient Algorithm [1.713291434132985]
  The knowledge gradient (KG) algorithm is a popular and effective algorithm for the best arm identification (BAI) problem. We present new theoretical results about the finite-time performance of the KG algorithm.
  arXiv  Detail & Related papers  (2022-06-14T13:42:05Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  We study a class of algorithms for solving bilevel optimization problems in both deterministic and deterministic settings. We exploit a warm-start strategy to amortize the estimation of the exact gradient. By using this framework, our analysis shows these algorithms to match the computational complexity of methods that have access to an unbiased estimate of the gradient.
  arXiv  Detail & Related papers  (2021-11-29T15:10:09Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• Learning Fast Approximations of Sparse Nonlinear Regression [50.00693981886832]
  In this work, we bridge the gap by introducing the Threshold Learned Iterative Shrinkage Algorithming (NLISTA) Experiments on synthetic data corroborate our theoretical results and show our method outperforms state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-10-26T11:31:08Z)
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets [82.74514886461257]
  min-max optimization algorithms encounter problems far greater because of the existence of periodic cycles and similar phenomena. We show that there exist algorithms that do not attract any points of the problem. We illustrate such challenges in simple to almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost
  arXiv  Detail & Related papers  (2020-06-16T10:49:27Z)

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.