Questions tagged [heuristics]
The heuristics tag has no usage guidance.
69 questions
7
votes
1
answer
829
views
Why are some heuristics successful?
Mathematicians sometimes use heuristics to form expectations about what might be true or false. For examples, see Matthew Emerton's answer to Why should I believe the Mordell Conjecture?, this blog ...
12
votes
0
answers
267
views
What is known about G. A. Croes
G. A. Croes is the author of the first description of the 2-opt moves heuristic for improving non-optimal traveling salesman tours:
Croes, G. A. “A Method for Solving Traveling-Salesman Problems.” ...
- 13.2k
0
votes
0
answers
92
views
Algorithm that can solve or approximate the solution to a combination problem
I have a computational problem on my hands and I would like your help.
Here is my problem (simplified)
Let $X = \{x_1, x_2, \ldots, x_n\}$ represent a set of $n$ values.
Each value $x_i$ has a ...
- 1
0
votes
0
answers
27
views
Heuristics for constrained maximal volumes in hypercubes as $n \to \infty$
It can be shown that there is a unique maximal surface of revolution with constant positive Gaussian curvature embedded in $[0,1]^3$ with a pair of antipodal points as cone points which attain the ...
- 383
2
votes
1
answer
133
views
Constructing optimal Hamilton cycles from optimal Hamilton paths
Question:
can the shortest Hamilton cycle in a complete symmetric graph with weighted edges be constructed from the shortest Hamilton path in the same graph by connecting its ends and then exchanging ...
- 13.2k
0
votes
0
answers
28
views
Calculation of cardinality constrained minimum weight matchings
Given a complete weighted graph $G(V,E),\ |V|=2n$, calculating a minimum weight matching with $n-k$ edges can be reduced to calculating a perfect matching in $H(V+U,E+F),\ |U|=2k,\ F=(u\in U,v\in V),\ ...
- 13.2k
0
votes
1
answer
74
views
Optimality of a "shopping" heuristic
Suppose the following situation: we have to buy $n$ goods $g_1,\,\dots,\,g_n$ starting at day 1 and we can't buy more than one good per day.
On day $d$ the prices are $p_1^d,\,\dots,\,p_n^d;\quad p_i^...
- 13.2k
9
votes
0
answers
189
views
Cyclic numbers of the form $2^n + 1$
A cyclic number (or cyclic order) is a number $m$ such that the only group of order $m$ is the cyclic group $\mathbb{Z}/m\mathbb{Z}$. The set of cyclic numbers admits a couple of cute number-theoretic ...
- 756
-2
votes
2
answers
149
views
Greedy euclidean tour expansion - a case of unexpected hanging?
In the euclidean plane an common heuristic for the TSP is to start with the convex hull of the point set and then successively integrate as the next point and insertion position the combination that ...
- 13.2k
0
votes
1
answer
38
views
Edge-length constraints from greedy matching
The subject of this question are perfect matchings of a complete undirected graph $G(V,E), n:=\mathrm{card}(V)=2k$, without self-loops or parallel edges and $n=2k$ vertices.
The objective is to ...
- 13.2k
2
votes
2
answers
355
views
Heuristic model for Lehmer pairs?
Rodgers and Tao proved that the De Bruijn–Newman constant $\Lambda$ is non-negative. The study of $\Lambda$ goes back at least to Lehmer's paper, On the roots of the Riemann zeta-function, whose ...
- 82.6k
0
votes
0
answers
26
views
Are there any examples of "autonomous" TSP heuristics
By "autonomous" TSP heuristic I mean algorithms whose reported edge-set for a short Hamilton cycle is invariant under the addition of vertex weights;
the terminology is borrowed from ...
- 13.2k
1
vote
0
answers
336
views
Heuristics for minimum path cover of undirected graph
Suppose you would like to find a set of paths on an undirected connected graph that ensures every vertex is visited exactly once while minimising the number of paths used. In this case, a "path&...
- 139
2
votes
1
answer
634
views
Factorial primes: expected finite or infinite?
A factorial prime is of the form $n! \pm 1$.
The first $14$ factorial primes are listed in
the Online Integer Sequences (OEIS)
A088054:
$$
2, 3, 5, 7, 23, 719, 5039, 39916801, 479001599, 87178291199, ...
- 151k
0
votes
1
answer
158
views
Heuristics for lightweighted "cubic" spanning trees
I have the problem of calculating a good approximation of the minimimum-weight spanning tree with vertex-degrees in $\lbrace 1,3\rbrace$ of a complete symmetric graph, without parallel edges or self-...
- 13.2k
1
vote
0
answers
45
views
Vertex cover via maximally unbalanced spanning trees
The vertex cover problem asks for a smallest subset $U\subseteq V$ that is adjacent to all edges of a symmetric graph $G(V,E)$.
Inspired by the observation that led to this question Perfectly balanced ...
- 13.2k
2
votes
1
answer
138
views
Generating short Hamilton cycles from complete graphs
Let $G(V,E)$ be a complete symmetric graph without self-loops or parallel edges; depending on the context the edges may however be interpreted as a pair of antiparallel arcs of equal weight.
A vertex ...
- 13.2k
5
votes
0
answers
192
views
Heuristics for the very little torsion in the cohomology of Shimura variety
Consider the following statement which is a part of Conjecture 1.3 in the paper titled "The asymptotic growth of torsion homology for arithmetic groups" authored by N. Bergeron and A. ...
- 443
0
votes
0
answers
55
views
Does LKH perform best with $\mathrm{1\unicode{x2013}trees}$
The LKH heuristic essentially generates sequence connected graphs with $n$ edges by means calculating minimum-weight spanning trees of $n-1$ of the vertices and connects the unspanned vertex to the ...
- 13.2k
0
votes
1
answer
126
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 ...
- 87
-1
votes
1
answer
243
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:
with a cycle defined here:
which ...
- 13.2k
3
votes
0
answers
166
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 ...
- 125
1
vote
1
answer
115
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 ...
- 13.2k
0
votes
0
answers
26
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 ...
- 13.2k
1
vote
1
answer
666
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 ...
- 13.2k
60
votes
9
answers
5k
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
33
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:\ \...
- 13.2k
9
votes
3
answers
1k
views
Books on the 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 ...
- 107
3
votes
0
answers
81
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 ...
- 1,013
2
votes
0
answers
97
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 ...
- 1,013
5
votes
0
answers
342
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.
$$
...
- 1,645
4
votes
1
answer
285
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 $\...
- 489
-2
votes
1
answer
174
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 ...
- 13.2k
0
votes
0
answers
33
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.
...
- 13.2k
1
vote
0
answers
27
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, ...
- 13.2k
3
votes
1
answer
369
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
227
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 ...
- 1,013
3
votes
0
answers
102
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 ...
- 31
4
votes
1
answer
700
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 $...
user6671
2
votes
0
answers
237
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 ...
user6671
0
votes
1
answer
101
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 ...
- 1,590
0
votes
0
answers
37
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 ...
- 13.2k
4
votes
2
answers
964
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 ...
- 3,699
58
votes
15
answers
9k
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 ...
14
votes
1
answer
2k
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 ...
- 5,380
1
vote
1
answer
130
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}...
- 13.2k
1
vote
0
answers
119
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 ...
- 4,049
3
votes
2
answers
208
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 ...
- 13.2k
5
votes
0
answers
238
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 \...
- 862
2
votes
1
answer
279
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 ...
- 13.2k