DISCOGAKT Research Seminar | Berlin Math Seminars

Tue, 27.02.24

TEL512 + online (...

Javier Cembrano

Impartial rank aggregation

Abstract.

We study functions that produce a ranking of n individuals from n such rankings and are impartial in the sense that the position of an individual in the output ranking does not depend on the input ranking submitted by that individual. When n ≥ 4, two properties concerning the quality of the output in relation to the input can be achieved in addition to impartiality: individual full rank, which requires that each individual can appear in any position of the output ranking; and monotonicity, which requires that an individual cannot move down in the output ranking if it moves up in an input ranking. When n ≥ 5, monotonicity can be dropped to strengthen individual full rank to weak unanimity, requiring that a ranking submitted by every individual must be chosen as the output ranking. Mechanisms achieving these results can be implemented in polynomial time. Both results are best possible in terms of their dependence on n. The second result cannot be strengthened further to a notion of unanimity that requires agreement on pairwise comparisons to be preserved. This is joint work with Felix Fischer and Max Klimm.

DISCOGAKT

Tue, 20.02.24 at 10:30

TEL512 + online

Ekin Ergen

Disbalance of Machines in Total Completion Time Scheduling Under Scenarios

Abstract.

We revisit the problem of scheduling unit-weight jobs onto parallel machines under scenarios. In our model, a scenario is defined as a subset of a predefined and fully specified set of jobs. The aim is to find a schedule of the whole set of jobs on parallel machines such that the schedule, obtained for the given scenarios by simply skipping the jobs not in the scenario, optimizes the average completion time over all scenarios (Bosman et al., 2023). In the first half of the talk, we recall total completion time scheduling under scenarios, painting an almost complete picture of its complexity landscape. We conjecture a structural property regarding load differences of machines of optimal schedules. This property implies a polynomial-time algorithm for a constant number of scenarios, settling the complexity of the problem. We discuss proven special cases of the conjecture, employing algorithmic ideas as well as tools from integer programming and polyhedral geometry. The second half of the talk is dedicated to a problem about the finiteness of a purely combinatorial process, which, depending on its solution, either proves another special case of the conjecture, or disproves the conjecture completely. We present examples, computational studies and observations. The first half of the talk is based on joint work with Thomas Bosman, Martijn van Ee, Csanad Imreh, Alberto Marchetti-Spaccamela, Martin Skutella and Leen Stougie. The second half is based on ongoing joint work with Martin Skutella and Maximilian Stahlberg.

DISCOGAKT

Tue, 23.01.24 at 16:15

TEL512

Norbert Zeh Dalhousie University

An FPT Algorithm for Scanwidth

Abstract.

Recently, Berry, Scornavacca, and Weller proposed scanwidth as a measure of how close a phylogenetic network is to being a phylogenetic tree. Much like the definition of the treewidth of a graph via the width of a tree decomposition of the graph, the scanwidth of a network is defined as the width of a rooted tree that reflects the structure of the network, called a tree extension of the network. In the same way that a low-width tree decomposition enables fast solutions to a wide range of NP-hard problems via dynamic programming over the tree decomposition, a low-width tree extension is expected to enable efficient dynamic programming solutions to various problems in phylogenetics (some examples of such problems exists already). This raises the question of how difficult it is to compute an optimal tree extension of a network. Berry, Scornavacca, and Weller proved that this problem is NP-hard. Holtgrefe proposed fast exponential-time algorithms, an XP-algorithm, and fast heuristics that appear to produce very good tree extensions in practice. In this talk, I will show how to reuse much of the machinery for computing an optimal tree decomposition of a graph to also compute an optimal tree extension of a phylogenetic network. The algorithm has running time O(f(k) * poly(n)), where k is the width of the computed tree extension (and f(.) is neither a completely crazy nor a particularly attractive function). Thus, our result proves that computing an optimal tree extension of a graph is fixed-parameter tractable when parameterized by the scanwidth of the network. I will also mention recent results on approximating the scanwidth of a network, as well as open problems. Joint work with: Niels Holtgrefe, Leo van Iersel, and Mark Jones

DISCOGAKT

Tue, 23.01.24 at 10:30

TEL512

Tim Oosterwijk VU Amsterdam

The Secretary Problem with Independent Sampling

Abstract.

The secretary problem is probably the most well-studied optimal stopping problem with many applications in economics and management. In the secretary problem, a decision-maker faces an unknown sequence of values, revealed one after the other, and has to make irrevocable take-it-or-leave-it decisions. Her goal is to select the maximum value in the sequence. While in the classic secretary problem, the values of upcoming elements are entirely unknown, in many realistic situations, the decision-maker still has access to some information, for example, in the form of past data. In this talk, I will take a sampling approach to the problem and assume that before starting the sequence, each element is independently sampled with probability p. This leads to what we call the random order and adversarial order secretary problems with p-sampling. In the former, the sequence is presented in random order, while in the latter, the order is adversarial. Our main result is to obtain the best possible algorithms for both problems and all values of p. As p grows to 1, the obtained guarantees converge to the optimal guarantees in the full information case, that is, when the values are i.i.d. random variables from a known distribution. Notably, we establish that the best possible algorithm in the adversarial order setting is a simple fixed threshold algorithm. In the random order setting, we characterize the best possible algorithm by a sequence of thresholds, dictating at which point in time we should start accepting a value. Surprisingly, this sequence is independent of p. I will then complement our theoretical results with practical insights obtained from numerical experiments on real life data obtained from Goldstein et al. (2020), who conducted a large-scale behavioral experiment in which people repeatedly played the secretary problem. The results help explain some behavioral issues they raised and indicate that people play in line with a strategy similar to our optimal algorithms from the first game onwards, albeit slightly suboptimally. This is joint work with José Correa, Andrés Cristi, Laurent Feuilloley, and Alexandros Tsigonias-Dimitriadis.

DISCOGAKT Research Seminar 📅