Randomized rounding refers to processes which, given a fractional point inside the convex hull of feasible integral points, randomly select an integral point while preserving the fractional point as the outcome’s expected value. Three communities, algorithms , statistics , and economics and computation , have studied randomized rounding mostly independently, focusing on different applications and properties. In algorithms, randomized rounding serves as a powerful tool for designing approximation algorithms, with emphasis on concentration properties. In statistics, it corresponds to probability-proportional-to-size sampling, where the stability of variance estimators is central. In economics and computation, randomized rounding enables fairness in allocation problems through lotteries, with emphasis on properties such as monotonicity.

In this Dagstuhl Seminar we want to bridge these streams of literature by bringing together experts from all three fields. Our discussions will center on the following goals:

• Goal I: Exchange of State of the Art and Open Problems. One central goal is to develop a shared language for randomized rounding across the three fields. With the help of the participants’ expertise, we aim to provide an overview of existing methods and the key desiderata and identify open problems that might benefit from techniques or perspectives developed in one of the other fields.
• Goal II: Rounding under Combinatorial Constraints. All three communities began with rounding methods for simple k-subsets and have since moved to increasingly complex combinatorial constraints. In algorithms, this includes bipartite matchings and matroids; in statistics, balanced sampling imposes constraints to limit overrepresentation; in economics and computation, combinatorial constraints appear when aiming for ex-post fairness conditions in participatory budgeting and fair allocation.
• Goal III: Online Rounding and Sampling. All three communities are increasingly adapting randomized rounding to online settings, where inputs arrive over time and rounding decisions must be made immediately and irrevocably. For example, in algorithms and economics and computation, online dependent rounding enabled advances in online matching and prophet inequalities. In parallel, the statistics literature has studied online sampling motivated by situations where data is too big to be fed into an algorithm and instead arrives in a data stream.
• Goal IV: Rules Satisfying Multiple Desiderata. Lastly, we aim to address the following natural question: Can a single rounding method meet the desiderata valued in different communities? Which combinations work, where are the trade-offs, and which insights might transfer across fields?

Creative Commons BY 4.0

José R. Correa, Paul Gölz, Claire Mathieu, and Ulrike Schmidt-Kraepelin

This seminar qualifies for Dagstuhl's LZI Junior Researchers program. Schloss Dagstuhl wishes to enable the participation of junior scientists with a specialisation fitting for this Dagstuhl Seminar, even if they are not on the radar of the organizers. Applications by outstanding junior scientists are possible until November 21, 2025.