# Questions tagged [heuristics]

A heuristic is a procedure that can apply generically to many problems (for example gradient descent, alternating optimization, simulated annealing) but will typically not have formal guarantees associated with its use.

50 questions
Filter by
Sorted by
Tagged with
152 views

1k views

### Heuristics for tsp without triangle inequality

Every heuristic for the traveling salesman problem that I know of (Nearest-Neighbour, Christofides, Held-Karp, ...) assumes that the triangle inequality holds. Are there heuristics to solve the tsp ...
• 227
202 views

### Exploring a DFA, with no feedback

Let $M=(\Sigma,S,s_0,\delta)$ be an (unknown) deterministic finite-state automaton (DFA), with alphabet $\Sigma$, statespace $S$, start state $s_0 \in S$, and transition relation $\delta$. I want to ...
• 12.1k
2k views

### Fast treewidth algorithms

I would like to compute the treewidth of a graph. There are really good heuristics for other NP-hard graph problems such as VF2 for subgraph isomorphism, with code available in igraph for example. I ...
• 3,902
2k views

### Approximation for metric TSP: Worst case using nearest neighbor heuristic?

I'm looking at different heuristics that approximate solutions for a metric Traveling Salesman Problem. I was wondering if there is a worst case ratio of tours calculated by the nearest neighbor ...
• 153
577 views

### Simplification of weighted NFA

What options does one have for the simplification (meaning reduction in the number of states) of weighted NFA over the probability semiring? From my understanding one can determinize, and then ...
• 81
160 views

### Find index set partition that has large projections

I have a multiset $S$ of $n$-bit strings. Let $1_S(s)$ denote the number of times that string $s$ appears in $S$, i.e., the multiplicity of $s$ in $S$. I want to find a partition of $\{1,2,\dots,n\}$...
• 12.1k
133 views

### Balanced partitioning of a set of axis-parallel 2D rectangles

Fix a constant $0<\alpha<1/2$. The problem is the following. Suppose there are $N$ axis-parallel rectangles on the 2D plane with weights $w_1, w_2,\ldots, w_N$ and with coordinates all in the ...
• 41
I'm teaching a course on meta-heuristics and need to generate interesting instances of classic combinatorial problems for the term project. Let's focus on TSP. We are tackling graphs of dimension $200$...