New answers tagged algorithms
2
As an approximation, suppose that the number $x$ of requests per trip does need to be an integer. Then $x$ needs to be at most $Q/q$ and divide $N$. For each fixed
$$x\in\{1,\dots,\min(N,\lfloor Q/q \rfloor): x \mid N\},$$
minimize $\sum_{i\in V} y_i$ subject to linear constraints
\begin{align}
(ax+b)n_i &\le T y_i &&\text{for $i\in V$} \\
x \...
4
The weight sum of all edges in the Eulerian tour created in Christofides algorithm is already at most $3/2$ times the weight sum of a TSP tour. While there are multiple ways of shortcutting the Eulerian tour into a Hamiltonian cycle, note that by the triangle inequality, any shortcut edge has a weight that is less than the total weight of the edges in the ...
Top 50 recent answers are included
