Questions tagged [heuristics]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4
votes
1answer
171 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 $\...
0
votes
0answers
20 views

Heuristics for the heaviest eulerian subgraph

Given a complete symmetric graph with $n=2k$ vertices and positive edgeweights, are there any better algorithms for determining the heaviest eulerian subgraph than this one that strives for finding ...
-1
votes
1answer
42 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
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. ...
1
vote
0answers
22 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
1answer
224 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 ...
0
votes
0answers
14 views

Generating sparse vertex-biconnected planar spanners of complete weighted graphs

Given a simple complete graph $\pmb{G}$ with weighted edges, what can be said about the following strategy of generating biconnected sparse planar spanners: Start: $\pmb{S}\ :=\ $a lightweight vertex ...
3
votes
1answer
152 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
0answers
64 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
1answer
420 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 $...
1
vote
0answers
166 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
1answer
60 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
0answers
26 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
2answers
604 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 ...
55
votes
16answers
5k 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 ...
5
votes
0answers
490 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
1answer
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
0answers
97 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
2answers
170 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
0answers
225 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
1answer
126 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
1answer
147 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 ...
1
vote
0answers
33 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
1answer
596 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 ...
70
votes
4answers
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
2answers
542 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
1answer
384 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
0answers
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
1answer
63 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 ...
31
votes
18answers
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
0answers
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
2answers
262 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
0answers
764 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
2answers
2k 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 ...
8
votes
0answers
731 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 ...
4
votes
1answer
466 views

class groups of unramified cyclic p-extensions of imaginary quadratic fields

Let $K$ be an imaginary quadratic number field with $p$-Sylow-class group $A(K)$ and $L/K$ be an unramified cyclic extension of $K$ of degree $p$ ($p$ prime). Then I am looking for heuristics on $...
9
votes
3answers
2k views

Groupoids vs Pseudogroups

(Warning: I'm not an expert in the topic) Let's work in a "geometric" category, for example the category $\mathfrak{Diff}$ of "manifolds" (without the requirements of connectedness and second ...
2
votes
1answer
201 views

Possible semantics for categorical co-constness

In category theory a morphism is constant IIF it is absorbing (for left composition). That is a morphism $k$ from $k:A\rightarrow B$ is constant if an only if for any two parrallel (same domain and ...
35
votes
6answers
70k views

Fourier vs Laplace transforms

In solving a linear system, when would I use a Fourier transform versus a Laplace transform? I am not a mathematician, so the little intuition I have tells me that it could be related to the boundary ...