smartphone webcam

To use the camera of a smartphone for a video conference on a computer, first an app is needed, which provides the image of the camera as a http stream, for example IP Webcam.

For Linux we can use v4l2loopback and ffmpeg to use the stream as a virtual webcam (here for the case that the smartphone has the IP

sudo modprobe v4l2loopback
ffmpeg -i -map 0:v -vcodec rawvideo -vf format=yuv420p -fflags nobuffer -flags low_delay -fflags discardcorrupt -f v4l2 /dev/video2

Additionally, one can use any filter ffmpeg offers, for example a colorkey or chromakey, to use any image background.jpg as a virtual background. Here for the case that a white sheet is used as a “green screen”:

ffmpeg -i images/background.jpg -i -vcodec rawvideo -fflags nobuffer -flags low_delay -fflags discardcorrupt -filter_complex "[1:v]colorkey=0xbbbbbb:0.3:0.2[foregroud];[0:v][foregroud]overlay[composite];[composite]format=yuv420p[out]" -map "[out]:v" -f v4l2 /dev/video2

Similarly, one can use the microphone of the smartphone as audio input for the computer. Here using pulseaudio and gstreamer:

pactl load-module module-null-sink sink_name="ipwebcam"
pactl set-default-source "ipwebcam.monitor"
gst-launch-1.0 souphttpsrc location="" is-live=true ! audio/x-raw,format=S16LE,layout=interleaved,rate=44100,channels=1 ! queue ! pulsesink device="ipwebcam"

Phase Transitions of Traveling Salesperson Problems solved with Linear Programming and Cutting Planes

In this Article, we introduce an ensemble of the Traveling Salesperson problem (TSP) that can be tuned with a parameter \(\sigma\) from the trivial case of cities equidistant on a circle to the random Euclidean TSP in a plane.

Einfach und schwierig zu lösende TSP Konfigurationen

For this ensemble we determine some phase transitions from an “easy” phase to a “not-that-easy” phase using linear programming. For each of these transitions we present structural properties of the optimal solution, which change at these points characteristically. Since the optimal solution is independent of the solution method, those phase transitions are not only relevant for the specific linear program respectively the solver implementation used to solve them, but a fundamental property of this TSP ensemble.

We used the classical linear program of Dantzig:

\begin{align} \label{eq:objective} &\text{minimize} & \sum_i \sum_{j<i} c_{ij} x_{ij}\\ \label{eq:int} &\text{subject to} & x_{ij} &\in \{0,1\}\\ %\mathbb{Z}\\ \label{eq:inout} & & \sum_{j} x_{ij} &= 2& & \forall i \in V \\ \label{eq:sec} & & \sum_{i \in S, j \notin S} x_{ij} &\ge 2& & \forall S \varsubsetneq V, S \ne \varnothing \end{align}

Here \(c_{ij}\) is the distance matrix between all pairs of cities of \(V\) and \(x_{ij}\) is the adjacency matrix, i.e., \(x_{ij} = 1\), if \(i\) and \(j\) are consecutive in the tour and \(x_{ij} = 0\) otherwise. Therefore, the first line minimizes the length of the tour. To avoid that we conclude that \(x_{ij} = 0\), i.e., staying at home, is identified as the optimal tour, we introduce the third line to force each city to have two connections, enough to enter and leave. But our salesman is clever and can trick us by choosing \(x_{ij} = 0.5\). Since we can not interpret this, we introduce line 2 to force all \(x_{ij}\) to integers. Still valid are two unconnected tours, which we forbid with the fourth line, the subtour elimination constraints. Well, the careful reader might already see that we defined one constraint for each subset of the cities, which are exponentially many in the number of cities. But we can solve this by starting without this class of constraints and only adding the ones which are actually violated by a solution. The violated ones can luckily be found easily by calculating the minimum cut of the proposed solution. The corresponding constraint can be added and the procedure is repeated until no subtour elimination constraint is violated anymore.

So does that mean that we found an efficient algorithm to solve the traveling salesperson problem? No, unfortunately we can not claim the Millenium Prize yet. There is no known algorithm which can efficiently solve this problem under the integer constraint. But if we drop this constraint, we can use efficient algorithms of linear programming to solve the relaxation. The resulting length will always be a lower bound on the actual solution and if we, by chance, find an integer solution, we can be sure that it is actually the optimal solution.

As the order parameter of the transitions from easy to hard we use the probability that a simplex solver yields an integer, and therefore optimal, solution. Without the Subtour Elimination Constraints, the transition occurs at the point at which the optimal solution deviates from the order of the cities on the initial circle. With the Subtour Elimination Constraints the transition coincides with the point at which the optimal tour changes from a zig-zag course to larger meandering arcs. This is measured by the tortuosity

\begin{align*} \tau = \frac{n-1}{L} \sum_{i=1}^{n} \left( \frac{L_i}{S_i}-1 \right). \end{align*}

which is maximal at this point. For the tortuosity the tour is divided in \(N\) parts of same-sign-curvature. For each part the ratio of the direct end-to-end distance \(S_i\) to the length along the arc \(L_i\) is summed.

So, we detected continuous phase transitions in the hardness of the problem with linear programming and correlated them with structural changes.

relay ssh

Connect via a server relay with target. Useful if target is behind a firewall, but reachable from relay.

ssh -J user1@relay user2@target

This can be combined with other options. This way a port forwarding can be established over which, e.g., sshfs can be used.

ssh -L 9999:localhost:22 -J user1@relay user2@target
sshfs user2@localhost:/path /mountpoint -C -p 9999

A combination with reverse-ssh could look like this:

ssh -L 9999:localhost:22 -J user1@relay -p 19999 user2@localhost