# Tagged Questions

Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.

58 views

56 views

### Early termination of A* with weak heuristic if solution is known

I have a large graph G and a pair of nodes s,t. I want to use the A* algorithm to find the shortest path from s to t, and I have a heuristic that is consistent. Suppose I already know of a path ...
24 views

47 views

### Linear time algorithm for finding $k$ shortest paths in unweighted graphs

Definition. Given an unweighted graph $G=(V,E)$ and two vertices $s$ and $t$, the $k$-shortest-paths problem is finding the $k$ shortest simple paths between $s$ and $t$ in $G$. Note that the ...
590 views

### Finding a fixed-size set whose members are contained by the largest number of other sets

I've been thinking about a problem, inspired by meeting a beginner-level foreign language professor at the Goethe-Institut who learned the five most common languages spoken by students in order to ...
30 views

### Is the prime factorization problem not an instance of the change making problem?

When using as the set of coins all logarithms of the prime numbers or numbers in general, and when using the logarithm of the number to be factored. The problem is just finding the logarithms that can ...
92 views

### Linear time algorithm for finding $k$ shortest paths from $s$ to $t$

Definition. Given a graph $G=(V,E)$ and two vertices $s$ and $t$, the $k$-shortest-paths problem is finding the $k$ shortest simple paths between $s$ and $t$ in $G$. Note that the length of ...
30 views

### Hyperplane through origin which goes through most number of points

Given $M$ points in $\mathbb{R}^{N}$ (where $M$ is larger than $N$), I was wondering if there is an algorithm to find a $N-1$-dimensional hyperplane which goes through the origin and also intersects ...
35 views

### Algorithm to enclose a 2D-gridbased-room efficient

I have the problem that I have a grid-based room which has 1 or more exits and I want to "secure" the room with minimal effort. Here a little Example: In this example black squares are not ...