TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Thu, 01 Jun 2023 05:15:07 GMT2023-06-01T05:15:07Z5061Solving packing problems with few small items using rainbow matchingshttp://hdl.handle.net/11420/6533Title: Solving packing problems with few small items using rainbow matchings
Authors: Bannach, Max; Berndt, Sebastian; Maack, Marten; Mnich, Matthias; Lassota, Alexandra; Rau, Malin; Skambath, Malte
Abstract: An important area of combinatorial optimization is the study of packing and covering problems, such as Bin Packing, Multiple Knapsack, and Bin Covering. Those problems have been studied extensively from the viewpoint of approximation algorithms, but their parameterized complexity has only been investigated barely. For problem instances containing no “small” items, classical matching algorithms yield optimal solutions in polynomial time. In this paper we approach them by their distance from triviality, measuring the problem complexity by the number k of small items.
Our main results are fixed-parameter algorithms for vector versions of Bin Packing, Multiple Knapsack, and Bin Covering parameterized by k. The algorithms are randomized with one-sided error and run in time 4k · k! · nO(1). To achieve this, we introduce a colored matching problem to which we reduce all these packing problems. The colored matching problem is natural in itself and we expect it to be useful for other applications. We also present a deterministic fixed-parameter algorithm for Bin Packing with run time O((k!)2 · k · 2k · n log(n)).
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11420/65332020-01-01T00:00:00ZOn the hierarchy of distributed majority protocolshttp://hdl.handle.net/11420/15038Title: On the hierarchy of distributed majority protocols
Authors: Berenbrink, Petra; Coja-Oghlan, Amin; Gebhard, Oliver; Hahn-Klimroth, Maximilian Grischa; Kaaser, Dominik; Rau, Malin
Abstract: We study the consensus problem among n agents, defined as follows. Initially, each agent holds one of two possible opinions. The goal is to reach a consensus configuration in which every agent shares the same opinion. To this end, agents randomly sample other agents and update their opinion according to a simple update function depending on the sampled opinions. We consider two communication models: the gossip model and a variant of the population model. In the gossip model, agents are activated in parallel, synchronous rounds. In the population model, one agent is activated after the other in a sequence of discrete time steps. For both models we analyze the following natural family of majority processes called j-Majority: when activated, every agent samples j other agents uniformly at random (with replacement) and adopts the majority opinion among the sample (breaking ties uniformly at random). As our main result we show a hierarchy among majority protocols: (j + 1)-Majority (for j > 1) converges stochastically faster than j-Majority for any initial opinion configuration. In our analysis we use Strassen’s Theorem to prove the existence of a coupling. This gives an affirmative answer for the case of two opinions to an open question asked by Berenbrink et al. [PODC 2017].
Thu, 01 Dec 2022 00:00:00 GMThttp://hdl.handle.net/11420/150382022-12-01T00:00:00ZDynamic averaging load balancing on arbitrary graphshttp://hdl.handle.net/11420/15126Title: Dynamic averaging load balancing on arbitrary graphs
Authors: Berenbrink, Petra; Hintze, Lukas; Hosseinpour, Hamed; Kaaser, Dominik; Rau, Malin
Wed, 01 Feb 2023 00:00:00 GMThttp://hdl.handle.net/11420/151262023-02-01T00:00:00ZEfficient approximate recovery from pooled data using doubly regular pooling schemeshttp://hdl.handle.net/11420/15128Title: Efficient approximate recovery from pooled data using doubly regular pooling schemes
Authors: Hahn-Klimroth, Maximilian Grischa; Kaaser, Dominik; Rau, Malin
Wed, 01 Mar 2023 00:00:00 GMThttp://hdl.handle.net/11420/151282023-03-01T00:00:00ZAsynchronous opinion dynamics in social networkshttp://hdl.handle.net/11420/15132Title: Asynchronous opinion dynamics in social networks
Authors: Berenbrink, Petra; Hoefer, Martin; Kaaser, Dominik; Lenzner, Pascal; Rau, Malin; Schmand, Daniel
Fri, 01 Jul 2022 00:00:00 GMThttp://hdl.handle.net/11420/151322022-07-01T00:00:00ZInference of a rumor's source in the independent cascade modelhttp://hdl.handle.net/11420/15133Title: Inference of a rumor's source in the independent cascade model
Authors: Berenbrink, Petra; Hahn-Klimroth, Maximilian Grischa; Kaaser, Dominik; Krieg, Lena; Rau, Malin
Abstract: We consider the so-called Independent Cascade Model for rumor spreading or epidemic processes popularized by Kempe et al.\ [2003]. In this model, a small subset of nodes from a network are the source of a rumor. In discrete time steps, each informed node "infects" each of its uninformed neighbors with probability p. While many facets of this process are studied in the literature, less is known about the inference problem: given a number of infected nodes in a network, can we learn the source of the rumor? In the context of epidemiology this problem is often referred to as patient zero problem. It belongs to a broader class of problems where the goal is to infer parameters of the underlying spreading model, see, e.g., Lokhov [NeurIPS'16] or Mastakouri et al. [NeurIPS'20].
In this work we present a maximum likelihood estimator for the rumor's source, given a snapshot of the process in terms of a set of active nodes X after t steps. Our results show that, for cycle-free graphs, the likelihood estimator undergoes a non-trivial phase transition as a function t. We provide a rigorous analysis for two prominent classes of acyclic network, namely d-regular trees and Galton-Watson trees, and verify empirically that our heuristics work well in various general networks.
Sun, 01 May 2022 00:00:00 GMThttp://hdl.handle.net/11420/151332022-05-01T00:00:00Z