# Questions tagged [heuristics]

The tag has no usage guidance.

67 questions
Filter by
Sorted by
Tagged with
88 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
24 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 ...
• 377
121 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 ...
• 12.9k
27 views

• 12.9k
187 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 ...
• 706
145 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 ...
• 12.9k
37 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 ...
• 12.9k
349 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 ...
• 81.3k
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.9k
1 vote
303 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
612 views

• 12.9k
1 vote
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,019
206 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 ...
• 12.9k