Abstracts

 

16. April 2021: Katarzyna Bozek (Universität zu Köln)

Titel: Data science of bioimages

Abstract:

In this talk I will introduce research done in my group “Data science of bioimages”. I will use my recent work on dense object tracking as an example to illustrate challenges of bioimage analysis as well as opportunities it presents for method advancement in computer vision. Across the various projects performed in my group we encounter challenges that often cannot be resolved with existing computer vision methods. Our solutions therefore require method development drawing knowledge not only from computer vision and machine learning but also from process parallelization or algorithm optimization. While computational biology has grown into an established field, the recent progress in deep learning gave rise to a new area of computer vision in biology with few yet existing standard methods.

---

18. Juni 2021: Antonios Antoniadis (University of Twente)

Titel: Minimizing Energy Consumption on Multiple Machines with Sleep States

Abstract:

The talk is about the problem of minimizing energy consumption on multiple machines with sleep states: We are given n jobs, each with a release date, a deadline and a processing time, and wish to schedule them on m parallel machines so as to minimize the total energy consumed. Machines can enter a sleep state and they consume no energy in this state. Each machine requires L units of energy to awaken from the sleep state and in its active state the machine can process jobs and consumes a unit of energy per unit time.

The core of the talk revolves around giving a 2-approximation algorithm for the single machine case. The algorithm is based on the solution of a linear programming relaxation, which can be decomposed into a convex combination of integer solutions. However none of them may be feasible since the linear programming relaxation has a strictly positive integrality gap. We discuss how such an integer solution can nevertheless be turned into a feasible solution without increasing the cost by too much. We outline how these ideas can be extended in order to obtain the first known constant approximation for the multiprocessor setting (with an approximation factor of 3), before concluding the talk by discussing how the latter algorithm can be adapted to obtain an approximation ratio of 2, and how one can circumvent the linear-programming formulation in order to obtain a combinatorial O(1)-competitive algorithm from the problem.

The talk is based on joint work with Naveen Garg, Gunjan Kumar and Nikhil Kumar (SODA '20).

---

23. Juli 2021: Andrés Cristi (Universidad de Chile)

Titel: Sample-driven optimal stopping: From the secretary problem to the i.i.d. prophet inequality

Abstract:

We take a unifying approach to single selection optimal stopping problems with random arrival order and independent sampling of items. In the problem we consider, a decision maker (DM) initially gets to sample each of N items independently with probability p, and can observe the relative rankings of these sampled items. Then, the DM faces the remaining items in an online fashion, observing the relative rankings of all revealed items. While scanning the sequence the DM makes irrevocable stop/continue decisions and her reward for stopping the sequence facing the item with rank i is Y_i. The goal of the DM is to maximize her reward. We start by studying the case in which the values Y_i are known to the DM, and then move to the case in which these values are adversarial.

In this talk I will first present a linear program that captures the performance of an algorithm in the case where the values are known, and take its continuous limit by infinitely extending the sequence. I will show how we can recover classic results in the area such as those for the secretary problem, and the minimum ranking problem.

Then, I will show how we can reformulate the linear program with an additional stochastic dominance constraint to capture the case where the values are adversarial. By using the same machinery we are able to pin down the optimal algorithm for this problem, obtaining the optimal competitive ratios for all values of p. Notably, we prove that as p approaches 1, our guarantee approaches 0.745, matching that of the i.i.d. prophet inequality.