# Questions tagged [heuristics]

The tag has no usage guidance.

63 questions
Filter by
Sorted by
Tagged with
10 views

### Counterexample to non-optimal symmetric edge detection heuristic

The undirected TSP problem allows for the efficient detection of Nonoptimal Edges for the Symmetric Traveling Salesman Problem It is also known that the edges that constitute to the heaviest perfect ...
137 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 ...
26 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 ...
24 views

### Simple-path decomposition of random tours

let $V$ denote a set of $n$ vertices, $\lbrace\lbrace v_i,v_j\rbrace\subset V\rbrace$ the set $E$ of edges and $\lbrace\omega_{ij}=\omega_{ji}\in\mathbb{R}:\lbrace i,j\rbrace\mapsto\omega_{ij}\rbrace$ ...
297 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 ...
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 ...
1 vote
121 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
413 views

1 vote
108 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 ...
### (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 ...