Winterterm 2023/24
When: 15:00 (CET) on Friday
Where: G-210 and via Zoom
https://uni-hamburg.zoom.us/j/94889228942?pwd=VTY5d3Y1NjJqbEdoaEpxc3pOM3RoZz09
Febuary 9
Hamed Hosseinpour
Rumors with Changing Credibility
Abstract: The study of randomized rumor spreading processes, which disseminate information on undirected graphs, has been a topic of extensive research. In this presentation, we introduce a recently published paper that unveils a generic framework for analyzing a broad class of such processes on regular graphs. Notably, the analysis presented is protocol-agnostic, requiring only the bounded on the expected proportion of newly informed vertices in each round and a natural negative correlation property.
This versatile framework empowers researchers to analyse various protocols, including PUSH, PULL, and PUSH-PULL, thereby extending prior investigations. A distinctive feature of this framework, unlike previous works, is its accommodation of message failures at any time $t\in \N$ with a probability of $1-q(t)$, where the credibility function $q(t)$ can take any form over time. This flexibility allows the modeling of real-world scenarios where the transmissibility of rumors may fluctuate, as observed in the spread of misinformation and viruses. Furthermore, the framework extends its applicability to dynamic graphs, enhancing its relevance and utility in understanding information diffusion processes in evolving network structures.
https://drops.dagstuhl.de/storage/00lipics/lipics-vol287-itcs2024/LIPIcs.ITCS.2024.86/LIPIcs.ITCS.2024.86.pdf
January 19
Speaker : Malin Rau
A Tight (3/2 + ε)-Approximation Algorithm For Demand Strip Packing
Abstract: We consider the Demand Strip Packing problem (DSP), in which we are given a set of jobs, each specified by a processing time and a demand.
The task is to schedule all jobs such that they are finished before some deadline D while minimizing the peak demand, i.e., the maximum total demand of tasks executed at any point in time.
DSP is closely related to the Strip Packing problem (SP), in which we are given a set of axis-aligned rectangles that must be packed into a strip of fixed width while minimizing the maximum height.
DSP and SP are known to be NP-hard to approximate to within a factor smaller than 3/2.
We present a tight (3/2 + ε)-approximation algorithm for DSP that runs in polynomial time for every constant ε > 0, improving upon the previous best approximation ratio of 5/3 +ε.
For achieving this best possible approximation guarantee, we prove a global structural result about all optimal solutions: either all jobs with demand greater than OPT/2 are sorted by this parameter and are scheduled one after the other, or the schedule can fit one extra job with demand OPT and width D/50 while maintaining a peak demand of at most (3/2+ε)OPT.
January 12
Lukas Hintze
More Efficient Simulation of Population Protocols via Interaction Graphs
We consider the efficient simulation of population protocols. In the population model, in each step, two of n identical agents are chosen uniformly at random. The chosen agents then update their discrete states according to a common transition function. We view the interactions as forming the edges of a random (directed) multigraph, with each additional interaction corresponding to the addition of a uniformly random edge. In a way, sampling this interaction multigraph is the ``hard part'' of simulating population protocols (at least when there are relatively few active states). The current state of the art [1] involves batch processing of interactions, where the batch size is determined (in the simplest version) by the number of interactions until an agent is selected for the second time, leading leads to batch sizes of Oh(sqrt(n)) interactions w.h.p. and in expectation. More generally, there is a processing in epochs, with epochs lasting until the ρth time any already-updated agent is selected again (for a carefully chosen ρ). In the graph point of view, this amounts to exactly sampling the number of interactions it takes for the interaction multigraph to first reach a certain complexity. We consider the reverse approach:
Instead of choosing a measure of complexity and sampling the hitting time of this complexity being reached, we choose an appropriate distribution of the number of interactions per batch, and then exactly sample the component structure of the interaction graph with that number of interactions. The distribution is chosen so that the degree histogram of the interaction graph is efficiently sampleable. We can then sample the component structure in the configuration model given the degree histogram, taking care to do this efficiently. This allows for batches of larger sizes (so far about n^(3/4) interactions per batch).
[1]: Berenbrink, Hammer, Kasser, Meyer, Penschuck, Tran - Simulating Population Protocols in Sub-Constant Time per Interaction. ESA 2020. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.16
December 22
Maarten Mäcking
Gefahrguttransport mit kooperierenden Robotern
In diesem Vortrag werden Algorithmen zur Sicherstellung eines Gefahrenobjekts mithilfe von kooperierenden Robotern unter verschiedenen Ausgangssituationen betrachtet und entwickelt.
An einem bestimmten Ort wurde eine Bombe entdeckt, welche um eine festgelegte Distanz von dem Fundort wegtransportiert werden muss. Für diese Aufgabe befinden sich mobile Roboter mit individuellen Maximalgeschwindigkeiten an beliebigen Punkten in der Ebene. Die Roboter können die Bombe untereinander weitergeben und gesammelte Informationen austauschen, wenn sie sich gegenüberstehen. Der Fokus besteht darin, Strategien zu finden, um die Bombe in einer möglichst kurzen Zeit aus der Gefahrenzone zu bringen.
Zunächst wird das Offline-Szenario betrachtet, bei dem die Positionen und Maximalgeschwindigkeiten der Roboter im Voraus bekannt sind. Hierzu wird ein optimaler Algorithmus für zwei sowie Approximationsalgorithmen für beliebig viele Roboter vorgestellt. Anschließend werden Algorithmen für verschiedene Online-Szenarien untersucht und untere sowie obere Schranken für deren Laufzeit etabliert. Die Online-Szenarien unterscheiden sich hinsichtlich des Wissens der Roboter über die sichere Entfernung der Bombe zum ursprünglichen Fundort sowie dem gemeinsamen Richtungsverständnis der Roboter.
November 24
Christoph Damerius
Improved Scheduling with a Shared Resource
We consider the following scheduling problem: A set of jobs j has to be scheduled, each of which has a volume v_j and a resource requirement r_j. A total resource of 1 is available at any time. A schedule may adjust the resources assigned to the jobs over time, but assigning the jobs less resource causes a proportional slowdown of the job.
First, we seek to minimize the makespan in an online setting, where the resource assignment of a job must be fixed before the next job arrives. Here we discuss a tight (e/(e-1))-competitive algorithm.
In our second model, we aim to minimize the total completion time. We use a continuous linear programming (CLP) formulation for the fractional total completion time and combine it with a previously known dominance property from malleable job scheduling to obtain a lower bound on the total completion time. We extract structural properties by considering a geometrical representation of a CLP's primal-dual pair. Combining the CLP schedule with a greedy schedule then gives us a (3/2+\varepsilon)-approximation, improving the previously best-known approximation factor of 2.
November 17
Christopher Hahn
A Mathematica tool for analysing chemical reaction networks
Abstract: In our field of research, problems are defined by precise mathematical models. Research questions are typically phrased as "Is there a protocol that satisfies property p?" or "Given the following protocol, what is the expected time until event e happens?" By solving one question, often new ones arise that can be phrased as "Can we apply the same analysis to a similar model?" On a high level, our research mostly looks like this:
Repeat the following until success:
1. Discuss which tools to use to approach the problem.
2. Manually manipulate mathematical expressions according to 1.
3. Evaluate if the results of 2. solve the problem.
Usually, research meetings end after step 1 with a list of mathematical expressions that need to be evaluated - leaving everyone in suspense. Often, the needed calculations are tedious, error-prone, but straightforward. Speeding up these calculations would enable us to go through several cycles in one meeting. Recently, I noticed that the calculations I did were almost identical. So I started to shift them from pen and paper to Mathematica by developing a specialized tool to do these calculations with the push of a button. With this talk, I hope to share my experience so far
November 10, 15:00 Uhr
Felix Biermeier
In this talk we present a variant of the biased opinion dynamics in the population model. We provide an overview of our currently incomplete state of analysis. We consider the well known undecided state dynamics with two opinions where one of them is the preferred opinion. The preferred one has a slight advantage compared to the other one. We define this advantage and analyse the convergence time of the protocol.
November 03
Thorsten Götte
Time-Optimal Construction of Overlay Networks
We show how to construct an overlay network of logarithmic degree and diameter in $O(\log n)$ time starting from an arbitrary weakly connected graph.
We assume a synchronous communication network in which nodes can send messages to nodes they know the identifier of and establish new connections by sending node identifiers.
Suppose the initial network's graph is weakly connected and has degree $d$. In that case, our algorithm constructs the desired topology with each node sending and receiving only $O(d\log n)$ messages in each round in $O(\log n)$ time, w.h.p., which beats the currently best $O(\log^{3/2} n)$ time algorithm of [Götte et al., SIROCCO'19].
Our algorithm is asymptotically optimal since the problem cannot be solved faster than by using pointer jumping for $O(\log n)$ rounds (which would even require each node to communicate $\Omega(n)$ bits).
We achieve this speedup by using short random walks to repeatedly establish random connections between the nodes that quickly reduce the conductance of the graph using an observation of [Kwok and Lau, APPROX'14].
Additionally, our algorithm can efficiently solve graph problems in so-called hybrid networks [Augustine et al., SODA'20].