Großteils kleingeistig
Welcome! I’m Manuel Sorge, researcher in theoretical computer science. News and ramblings:
-
Temporal Clustering
Paper summary ·Clustering data is a basic task and has gotten immense attention, in particular graph-based clustering, where we are given pairwise relationships between people, say, and we want to group them into well-connected clusters with fewer connections between clusters.
Here is an interesting relatively new twist on this kind of problem [1]: Instead of static data, like in a...
-
Improving your Facebook feed / Maximizing closeness and betweenness centrality
News ·One sentence summary: Increasing your importance in Facebook by making new friends is quite hard in theory.
Say you could befriend any k persons on Facebook. Who would you add so that you get the most out of your feed? That seems hard to measure but let’s suppose that your feed gets more useful the more central you are in...
-
Paper published: Iteratively recognizing core-periphery structure
News ·One-sentence summary: Recognizing graph properties can be done efficiently by adding vertices one-by-one, perhaps destroying the property, and then repairing it.
The original motivation of this paper is a problem related to checking for core-periphery structure in graphs [1], for example, in social networks. The idea is that such networks consist of a densely connected core, and a...
-
Paper published: Approximate Arc Routing
News ·One sentence summary: We show how to find approximate solutions for arc routing problems using approximation algorithms for the traveling salesman problem.
A very general problem in arc routing is the Capacitated Arc Routing Problem, where we want to route a fleet of vehicles in an in total shortest possible way so to service a given number of streets in...