# Questions tagged [heuristics]

The tag has no usage guidance.

55 questions
Filter by
Sorted by
Tagged with
0answers
8 views

### Terminal set of iterated edge-filtering

Given a finite symmetric graph $G(V,E)$ with randomly weighted edges, what will the set of edges be that survives the following refiltering process that is repeated until no edges exist that satisfy ...
1answer
105 views

### Nicely motivated papers or book chapters on the formula for the sum of the $k$-th powers of the first natural numbers [closed]

Do you know of a text where I can find a nicely motivated proof of the formula for $1^{k}+2^{k}+\cdots+n^{k}$? At the very beginning of page 68 of Professor H. S. Wilf's generatingfunctionology, one ...
1answer
170 views

### Helsgaun's $k$-Opt moves

In his 2009 paper General k-opt submoves for the Lin–Kernighan TSP heuristic, Helsgaun defines the local tour improvements on which the LKH heuristics are based as: several questions arise from that ...
0answers
133 views

### Are class numbers of number fields with prime degree often $1$?

I have taken a look at the class number statistics of the L-functions and Modular Forms Database: https://www.lmfdb.org/NumberField/stats, table "Distribution by class number". It appears ...
0answers
19 views

### Probability that edge exchange yields a tour

let $H$ be a Hamilton cycle in a complete topological symmetric graph $G$ of finite size. Question: what is the probability that a vertex-disjoint cycle cover $C_k$ that is generated from $H$ by ...
1answer
41 views

### $\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves

$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong ...
0answers
34 views

### Examples of recursive TSP heuristics

Question: What are examples of heuristics for the Traveling Salesman Problem, that are recursive in the sense that they can efficiently calculate the shortest Hamilton cycle in a graph if the optimal ...
0answers
19 views

### Complexity of heaviest 2-optimal vertex-disjoint cycle covers

Calculating lightest vertex-disjoint cycle covers of finite complete symmetric graphs with weighted edges can be done efficiently and also renders the edge set of the calculated cycles free of pairs ...
0answers
36 views

### How to prevent spanning trees from spiraling

Spanning trees and especially minimum spanning trees are the anchor point of a whole class of TSP heuristics, most prominently the Christofides algorithm. I noticed however that there may be MSTs for ...
1answer
56 views

### Calculating vertex weights

Vertex weights are a metaphor for a constant value $\pi_i$ that is added to the weight of every edge $e_{ij}$ that is adjacent to vertex $v_i$ in a symmetric graph $G(V,E)$ with weighted edges. The ...
0answers
15 views

### Rationale behind partitioning heuristic for Euclidean MWTs

Finding Minimum Weight Triangulations of planar pointsets is NP-hard, whereas it can be solved in $O(n^3)$ with backtracking for simple polygons. A fairly popular heuristic for calculating ...
9answers
4k views

### Examples of back of envelope calculations leading to good intuition?

Some time ago, I read about an "approximate approach" to the Stirling's formula in M.Sanjoy's Street Fighting Mathematics. In summary, the book used a integral estimation heuristic from ...
0answers
21 views

1answer
59 views

### What is known about iterated matching as a TSP heuristic

A fairly wellknown heuristic for TSP that is based on matching is described in the 2003 paper Match twice and stitch: a new TSP tour construction heuristic by Andrew B. Kahng and Sherief Reda. Its ...
0answers
32 views

### Reasons for inapplicability of complete induction to tour expansion

It is known that tour expansion is a rather poor heuristic for generating short Hamilton cycles even in the planar Euclidean case. That comes as a surprise when learning of that for the first time. ...
0answers
23 views

### Complexity of tour-expansion heuristic for the planar Euclidean TSP

This is a followup question to this one: Computational Geometric Aspects of Greedy Tour Expansion. Assume that the candidate point, whose insertion into current incurs the least tour-length increase, ...
1answer
240 views

### Is there a clear criterion or rule about when one can use the heuristic given by Cramér random model for prime numbers?

I don't know if I have misunderstood the information from the section about the heuristic related to Cramér's conjecture and the known facts about Maier's theorem, from the Wikipedia Cramér's ...
1answer
183 views

### How can we justify the use of Example 5,4 (of Cohen, Lenstra) assuming their heuristics

In these days, I'm studying Cohen-Lenstra heuristics to understand the paper of Rene Schoof "Class Numbers of Real Cyclotomic Fields of Prime Conductor". On page 932 of Schoof's paper, there is a ...
0answers
65 views

### Matching of two weighted graphs allowing one-to-many mapping

I am looking for a heuristic for a graph matching problem as follows. Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than ...
1answer
504 views

0answers
100 views

### Heuristics for this “subset” traveling salesman problem

Are there any known heuristics for the following variation of the traveling salesman problem: given $n$ sets of points $S_1,\dots,S_n$, and $n$ integers $k_i$ such that $k_i \leq |S_i|$, find the ...
2answers
175 views

### (How) do Better TSP Heuristics help in Answering the $NP=P$ Question?

This question is motivated by my impression, that finding better heuristics for the TSP problem (or any other $NP$-complete problem) is "only" of practical interest, but doesn't provide any progress ...
0answers
233 views

3answers
3k views

### Defining the slowest divergent series

This question might seem too fuzzy, and if so, I will be happy to withdraw it. Until then, here it is: I know that a method of slowing a divergent series of positive reals is to replace the $n$-th ...