An Upper Bound for Minimum True Matches in Graph Isomorphism with Simulated Annealing
Graph matching is one of the most important problems in graph theory and combinatorial optimization, with many applications in various domains. Although meta-heuristic algorithms have had good performance on many NP-Hard and NP-Complete problems, for this problem there are not reported superior solutions by these algorithms. The reason of this inefficiency has not been investigated yet. In this paper we show that simulated annealing as an stochastic optimization method is unlikely to be even close to the optimal solution for this problem. In addition to theoretical discussion, the experimental results also verified our idea; for example, in two sample graphs, the probability of reaching to a solution with more than three correct matches is about $0.02$ in simulated annealing.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationGraph MatchingStochastic OptimizationSimilar Papers 제목 키워드 기반
Learning Performance Bounds for Safety-Critical Systems
As the complexity of control systems increases, the need for systematic methods to guarantee their efficacy grows as well. However, direct testing of these systems is oftentimes costly, difficult, or impractical. As a re…
Bayesian OptimizationTranslationHow Well Do Local Algorithms Solve Semidefinite Programs?
Several probabilistic models from high-dimensional statistics and machine learning reveal an intriguing --and yet poorly understood-- dichotomy. Either simple local algorithms succeed in estimating the object of interest…
Minimum Width of Deep Narrow Networks for Universal Approximation
Determining the minimum width of fully connected neural networks has become a fundamental problem in recent theoretical studies of deep neural networks. In this paper, we study the lower bounds and upper bounds of the mi…
Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem
We study the $K$-armed dueling bandit problem, a variation of the standard stochastic bandit problem where the feedback is limited to relative comparisons of a pair of arms. We introduce a tight asymptotic regret lower b…
Best Policy Identification in Linear MDPs
We investigate the problem of best policy identification in discounted linear Markov Decision Processes in the fixed confidence setting under a generative model. We first derive an instance-specific lower bound on the ex…