# Questions tagged [heuristics]

The tag has no usage guidance.

62 questions
Filter by
Sorted by
Tagged with
28 views

### The best of two worlds for TSP heuristics

Let $G$ be a finite, simple graph with weighted edges. The objective of TSP heuristics is to find a Hamilton cycle in $G$ that comes close to the ideal of being the shortest possible. From that ...
257 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 ...
8 views

### Non-optimality of an edge shared between the initial subtour and the optimal cycle cover

Suppose we have an initial tour $T_0$ on which the vertices are encountered in the same order in which they will be encountered on the optimal tour $T_{OPT}$ (in the planar Euclidean case the convex ...
24 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 ...
14 views

Let $T=\lbrace t_{i,\pi(i)}\rbrace\subset E,\ S=\lbrace s_{ij}\rbrace =E\setminus T$ denote the set of tour edges, resp. of tour "secants". Let $\lbrace x_{i,\pi(i)}\rbrace \in \lbrace 0,1\... 1 vote 0 answers 96 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&... 1 vote 1 answer 274 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, ... 0 votes 1 answer 60 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-... 1 vote 0 answers 28 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 ... 2 votes 1 answer 119 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 ... 4 votes 0 answers 167 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. ... 0 votes 0 answers 29 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 ... 0 votes 0 answers 20 views ### Tour expansion with min-cost flow Question: has the problem of formulating optimal tour-expansion for Symmetric TSP's already been mentioned as a means for faster tour-expansion in the sense of potentially intergrating more than one ... 0 votes 1 answer 113 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 222 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 ... 3 votes 0 answers 153 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 ... 1 vote 1 answer 66 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 22 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 ... 1 vote 1 answer 201 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 ... 57 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 25 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:\ \... 8 votes 3 answers 996 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 ... 3 votes 0 answers 74 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 87 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 245 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 225 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 81 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 24 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 277 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 188 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 68 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 586 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$... 190 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 ... 78 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 ...
29 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 ...
728 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 ...
7k 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 ...
850 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
116 views

220 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 ...
151 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 ...
42 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, ...
670 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 ...
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....
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 ...
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 ...