Dagstuhl-Seminar 26242
Randomized Rounding in Algorithms, Statistics, and Economics and Computation
( 07. Jun – 12. Jun, 2026 )
(zum Vergrößern in der Bildmitte klicken)
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/26242
Organisatoren
- José R. Correa (University of Chile - Santiago de Chile, CL)
- Paul Gölz (Cornell University - Ithaca, US)
- Claire Mathieu (CNRS - Paris, FR)
- Ulrike Schmidt-Kraepelin (TU Eindhoven, NL)
Kontakt
- Michael Gerke (für wissenschaftliche Fragen)
- Susanne Bach-Bernhard (für administrative Fragen)
Dagstuhl Reports
As part of the mandatory documentation, participants are asked to submit their talk abstracts, working group results, etc. for publication in our series Dagstuhl Reports via the Dagstuhl Reports Submission System.
- Upload (Use personal credentials as created in DOOR to log in)
Dagstuhl Seminar Wiki
- Dagstuhl Seminar Wiki (Use personal credentials as created in DOOR to log in)
Gemeinsame Dokumente
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
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.
Please log in to DOOR to see more details.
- Katherine Brumberg
- Javier Cembrano
- Guillaume Chauvet
- José R. Correa
- Gabrielle Demange
- Benjamin Doerr
- Sharmila Duppala
- Paul Gölz
- Svenja M. Griesbach
- Calum MacRury
- Claire Mathieu
- Dominik Peters
- Louis-Paul Rivest
- Ulrike Schmidt-Kraepelin
- Golnoosh Shahkarami
- Ana-Andreea Stoica
- Yves Tillé
- Jamie Tucker-Foltz
- Markus Utke
- Rohit Vaish
- Victor Verdugo
- Jan Vondrak
- David Wajc
Klassifikation
- Computer Science and Game Theory
- Data Structures and Algorithms
Schlagworte
- dependent randomized rounding
- sampling
- algorithms
- statistics
- economics and computation
