# Questions tagged [heuristics]

The heuristics tag has no usage guidance.

55
questions

**0**

votes

**0**answers

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 ...

**0**

votes

**1**answer

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 ...

**-1**

votes

**1**answer

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 ...

**3**

votes

**0**answers

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 ...

**0**

votes

**0**answers

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 ...

**1**

vote

**1**answer

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 ...

**0**

votes

**0**answers

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 ...

**0**

votes

**0**answers

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 ...

**0**

votes

**0**answers

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 ...

**1**

vote

**1**answer

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 ...

**0**

votes

**0**answers

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 ...

**53**

votes

**9**answers

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 ...

**1**

vote

**0**answers

21 views

### Calculating vertex weights via mutually tangent circles of triangles

given a metric graph with positive edge weights $\left|e_{ij}\right|$ a standard task, especially in the context of the Traveling Salesman Problem, is to calculate $\max\sum\limits_{i=1}^n\omega_i:\ \...

**7**

votes

**2**answers

747 views

### Books on relationship between the Socratic method and mathematics?

Apart from books on heuristics by George Polya.
When trying to engage with and understand mathematical concepts and when applying abstract mathematical concepts to model "continuum" or real ...

**0**

votes

**0**answers

27 views

### Is this the worst case for the tour-expansion heuristic?

The tour-expansion heuristic is especially intriguing for the Euclidean Traveling Salesman Problem: start with the convex hull of the finite point-set and repeatedly insert of the remaining points the ...

**3**

votes

**0**answers

72 views

### I have a question on the definition of 'good' primes in the paper of Cohen and Martinet

I'm reading the paper of Cohen and Martinet 'Etude heuristique des groups de classes'.
In the section 6, for an central idempotent $e$ of $\mathbb{Q}[\Gamma]$ and a prime $p$, the 'goodness' of $p$ is ...

**2**

votes

**0**answers

82 views

### Is there any good reference on the Bayesian view that can be helpful for reading papers on the number theory using heuristic arguments?

Nowadays there are many papers on the number theory using heuristics.
I have read some of them.
But I have no clear understanding of the Bayesian Probability(subjective probability).
The concept of ...

**5**

votes

**0**answers

177 views

### Heuristic for a density conjecture related to the Collatz $(3x+1)$-problem

First, some notation. Define $T(n)$ over $n\in \mathbb{N}$ as:
$$
T(n) = \left\{ \begin{array}{}
3n+1, & \text{if $n$ is odd}\ \\
n/2, & \text{if $n$ is even}
\end{array} \right.
$$
...

**4**

votes

**1**answer

202 views

### Idea behind Carleson's theorem modern proof “intitial reductions”

I'm having troubles to understand the philosophy behind the modern proof of Carleson's theorem. For convenience, let me state precisely what I am asking for.
For any $f \in L^2(\mathbb{R})$, let $\...

**-1**

votes

**1**answer

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 ...

**0**

votes

**0**answers

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.
...

**1**

vote

**0**answers

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, ...

**3**

votes

**1**answer

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 ...

**3**

votes

**1**answer

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 ...

**3**

votes

**0**answers

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 ...

**4**

votes

**1**answer

504 views

### Does multiplication increase entropy?

Does multiplication increase entropy?
The Shannon entropy of a number $k$ in binary digits is defined as
$$ H = -\log(\frac{a}{l})\cdot\frac{a}{l} - \log(1-\frac{a}{l})\cdot (1-\frac{a}{l})$$
where $...

**2**

votes

**0**answers

177 views

### Heuristic for lower bounding the time for integer factorization?

I am posting this question here in hope that someone finds this heuristic useful, and maybe someone with more experience will make use of this:
As @GerryMyerson suggested here is a statement of what ...

**0**

votes

**1**answer

71 views

### Can time-scale calculus be used to derive a counterpart theorem of discrete-time dynamic systems directly from continuos-time dynamics systems?

From what I read of time-scale calculus literature, most results of continuous-time and discrete-time systems can be generalized to arbitrary time-scales by considering the generalized derivative ...

**0**

votes

**0**answers

27 views

### Generating Biconnected Graphs from Spanning Trees

Background of my question is an idea for generating an initial subtour for general symmetric TSPs:
Add to a MST a set of edges with minimal weight sum, that renders the resulting graph free of ...

**3**

votes

**2**answers

662 views

### Heuristics behind the Circle problem?

Is there a heuristic argument behind the exponent in the circle problem? The problem that I am referring to is the following: Consider a circle of radius $R$ centered at the origin in the plane and ...

**56**

votes

**15**answers

6k views

### What are examples of books which teach the practice of mathematics?

One may classify the types of mathematics books written for students into two groups: books which merely teach mathematics (i.e., they present theorems and proofs, ready-made, as it were) and those ...

**7**

votes

**0**answers

699 views

### Why do we mainly integrate with respect to martingales?

Although my resarch focuses on PDEs (optimal transport, these days), I am currently trying to learn stochastic calculus and integration. I am just beginning in this topics, but I was wondering: why do ...

**1**

vote

**1**answer

113 views

### Computational Geometric Aspects of Greedy Tour Expansion

Has the following problem already been investigated from the Computational Geometry point of view and what are the results regarding worst case complexity?
Given
a finite set $\mathcal{P}...

**1**

vote

**0**answers

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 ...

**3**

votes

**2**answers

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 ...

**5**

votes

**0**answers

233 views

### The set of numbers $a+b$ such that $ma^2+nb^2$ is prime

Conjecture:
If $m,n$ are coprime it exist a minimal natural number $N_{mn}$ such
that:
$\{a+b>N_{mn}\mid a,b\in\mathbb N^+\wedge ma^2+nb^2\in\mathbb P_{>2}\} = \{ k > N_{mn} \mid \...

**2**

votes

**1**answer

182 views

### Worst Case Region for a Convex Hull Heuristic

I am currently implementing a heuristic algorithm for planar convex hulls hand would like to know, for which kind of strictly convex region it exhibits worst performance.
I know that there are many ...

**2**

votes

**1**answer

148 views

### Heuristics for counting degrees of freedom

I have recently learned about the representation theorem for isotropic,
linear operators, which says the following:
Defintion:
Let $M_n$ be the vector space of $n \times n$ real matrices. We say a ...

**2**

votes

**0**answers

37 views

### Performance guarantee of RLF [closed]

I cannot manage to find the performance guarantee of the Recursive Largest First (RLF) algorithm for approximating the chromatic number of a graph.
I know DSATUR has a $\mathcal{O}(n)$ guarantee, ...

**4**

votes

**1**answer

615 views

### Heuristic probabilistic argument for the Navier-Stokes existence and smoothness conjecture

The Collatz Conjecture is a famous conjecture that has never been proven; nevertheless, there exists a simple heuristic probabilistic argument which supports its truth - in Wikipedia's words, "If one ...

**72**

votes

**4**answers

4k views

### What are reasons to believe that e is not a period?

In their 2001 paper defining periods, Kontsevich and Zagier (pdf) without further comment state that $e$ is conjecturally not a period while many other numbers showing up naturally (conjecturally) are....

**2**

votes

**2**answers

561 views

### Categories with binary relations as objects

For the category of functions, pairs of functions making commutative diagrams are the canonical morphisms $\alpha:f\rightarrow g$. For binary relations there is an alternative, to consider the ...

**7**

votes

**1**answer

411 views

### Cohen-Lenstra heuristics for totally complex fields

If a number field $K$ is a Galois extension of $\mathbb{Q}$, and $G = \operatorname{Gal}(K/\mathbb{Q})$, then the class group of $K$ is a $\mathbb{Z}[G]$-module, and since $N = \sum_{g \in G} g$ acts ...

**1**

vote

**0**answers

137 views

### Reduce a Combinatorial problem

It is given n sets with k vectors. (k is element-wise positive or zero)
Choose one vector of each set so that the biggest element of the sum of the chosen vectors is minimal.
What i also know but is ...

**1**

vote

**1**answer

64 views

### Heuristic for choosing n-vectors from n-sets

my given problem is:
choose n-vectors from n-sets (one vector from each set) so that the biggest element in the sum of the chosen vectors is minimal. Unfortunately the problem is NP-hard. So I'm ...

**33**

votes

**18**answers

5k views

### Non-rigorous reasoning in rigorous mathematics

I was wondering what role non-rigorous, heuristic type arguments play in rigorous math. Are there examples of rigorous, formal proofs in which a non-rigorous reasoning still plays a central part?
...

**1**

vote

**0**answers

177 views

### unfolding as resolution

Has anyone described 'unfolding' as used in mathematical physics (e.g. on-shell AND off-shell) as analogous to a resolution in algebra - higher derivatives are unfolded in terms of new variables?

**4**

votes

**2**answers

264 views

### Formula in common: How to search for same/similar equations in other knowledge domains?

Hi people
In a recent presentation by Sedgewick, he recounts in 1977 Flajolet noticed that they had a formula in common, both in different domains (see slide 4 in http://www.cs.princeton.edu/~rs/...

**12**

votes

**0**answers

796 views

### What is the intuition for $\mathbb{Q}^{ab}$ having cohomological dimension $1$?

I frequently talk to people who think of finite fields as arithmetic analogs of punctured discs. This makes some sense: the absolute Galois group of a finite field is the profinite completion of $\...

**10**

votes

**3**answers

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 ...