# Tag Info

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