Algorithms and Theory

Motivated by online decision-making in time-varying combinatorial environments, we study the problem of transforming offline algorithms to their online counterparts. We focus on offline combinatorial problems that are amenable to a constant factor approximation using a greedy algorithm that is robust to local errors. For such problems, we provide a general framework that efficiently transforms...

As recent literature has demonstrated how classifiers often carry unintended biases toward some subgroups, deploying machine learned models to users demands careful consideration of the social consequences. How should we address this problem in a real-world system? How should we balance core performance and fairness metrics? In this paper, we introduce a MinDiff framework for regularizing...

An ε-incidence between a point q and some curve c (e.g., line or circle) in the plane occurs when q is at (say, Euclidean) distance at most ε from c. We use variants of the recent grid-based primal-dual technique developed by the authors [ESA 2017, SoCG 2019] to design an efficient data structure for computing an approximate depth of any query point in the arrangement A(S) of a collection S of...

Missing data is a crucial issue when applying machine learning algorithms to real-world datasets. Starting from the simple assumption that two batches extracted randomly from the same dataset should share the same distribution, we leverage optimal transport distances to quantify that criterion and turn it into a loss function to impute missing data values. We propose practical methods to...