Questions tagged [heuristics]
The heuristics tag has no usage guidance.
29
questions with no upvoted or accepted answers
12
votes
0
answers
875
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 $\...
9
votes
0
answers
180
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 ...
- 606
8
votes
0
answers
780
views
Two different ways to count Mersenne Primes
Hi there, the motivation for this question is to better understand the heuristics of Mersenne primes, and I was motivated by the recent questions (Mersenne quasi-primes) and (Primes in generalized ...
5
votes
0
answers
189
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. ...
- 411
5
votes
0
answers
318
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,625
5
votes
0
answers
237
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 \...
- 852
3
votes
0
answers
161
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
3
votes
0
answers
80
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,043
3
votes
0
answers
97
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
2
votes
0
answers
95
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,043
2
votes
0
answers
223
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
1
vote
0
answers
263
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
1
vote
0
answers
41
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 ...
- 12.7k
1
vote
1
answer
103
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 ...
- 12.7k
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:\ \...
- 12.7k
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, ...
- 12.7k
1
vote
0
answers
118
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,929
1
vote
0
answers
140
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 ...
- 11
1
vote
0
answers
181
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?
- 3,850
0
votes
0
answers
22
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),\ ...
- 12.7k
0
votes
0
answers
13
views
Identifying optimization-potential in weighted Hamilton cycles
From the (possibly incorrect) assumption that inoptimality of weighted Hamilton cycles, that resemble a heuristic solution to a TSP problem, can be identified by calculating the MST (minimum spanning ...
- 12.7k
0
votes
0
answers
20
views
LP formulation of $k$-opt moves
Question:
what is known about formulating $k$-opt moves that strive for improving the length of Hamilton cycles by means of exchanging $k$ of the tour edges with $k$ non-tour edges?
Specifically:
are ...
- 12.7k
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 ...
- 12.7k
0
votes
1
answer
139
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-...
- 12.7k
0
votes
0
answers
49
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 ...
- 12.7k
0
votes
0
answers
23
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 ...
- 12.7k
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.
...
- 12.7k
0
votes
0
answers
32
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 ...
- 12.7k
-2
votes
1
answer
166
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 ...
- 12.7k