Noticias en español
Prophet Inequalities via the Expected Competitive Ratio.
Abstract: We consider prophet inequalities under general downward-closed constraints. In a prophet inequality problem, a decision-maker sees a series of online elements and needs to decide immediately and irrevocably whether or not to select each element upon its arrival, subject to an underlying feasibility constraint. Traditionally, the decision-maker’s expected performance has been compared to the expected performance of the prophet, i.e., the expected offline optimum. We refer to this measure as the Ratio of Expectations (or, in short, RoE). However, a major limitation of the RoE measure...
Read MoreMachine Covering in the Random-Order Model.
Abstract: In the Online Machine Covering problem, jobs, defined by their sizes, arrive one by one and have to be assigned to m parallel and identical machines, with the goal of maximizing the load of the least-loaded machine. Unfortunately, the classical model allows only fairly pessimistic performance guarantees: The best possible deterministic ratio of m is achieved by the Greedy-strategy, and the best known randomized algorithm has competitive ratio Õ(m^(1/2)), which cannot be improved by more than a logarithmic factor. In this talk, we will discuss results for the Machine Covering...
Read MoreAugmenting Online Algorithms with ε-Accurate Predictions.
Abstract: The growing body of work in learning-augmented online algorithms studies how online algorithms can be improved when given access to ML predictions about the future. Motivated by ML models that give a confidence parameter for their predictions, we study online algorithms with predictions that are $\epsilon$-accurate: namely, each prediction is correct with probability (at least) $\epsilon$, but can be arbitrarily inaccurate with the remaining probability. We show that even with predictions that are accurate with a small probability and arbitrarily inaccurate otherwise, we can...
Read MoreDifferentially Private Stationary Points in Stochastic Nonconvex Optimization.
Abstract: Differentially private (DP) stochastic nonconvex optimization (SNCO) is a fundamental problem, where the goal is to approximate stationary points (i.e points with small norm of the gradient) of the population loss, given a dataset of i.i.d. samples from a distribution, while satisfying differential privacy with respect to the dataset. Most of the existing works in the literature have addressed either the convex version of this problem (DP-SCO) or the closely related problem of Private Non-Convex Empirical Risk Minimization, where one seeks to approximate stationary points of the...
Read MoreComputing buyer-optimal Walrasian prices in multi-unit matching markets via a sequence of max flow computations.
Abstract: Given a market where discrete indivisible items of different types are sold to a set of buyers. There is a given supply of each type and each buyer has a given (maximum) demand. Each buyer valuates the items linearly in our setting. We aim for competitive prices, i.e. prices such that an allocation exists where every buyer gets one of his preferred bundles. The prices should be as small as possible and as much as possible should be sold. We show how to compute these buyer-optimal Walrasian prices. We present an ascending auction which iteratively raises the prices on the goods in...
Read MoreThe AGM Bound.
Abstract: In several computer science applications one encounters the following problem: Given two edge-labeled graphs G and H, how many homomorphic images of H can be found in G? Atserias, Grohe, and Marx developed a tight bound for this number, denoted #Hom(H,G), which is now known as the AGM bound. The bound relates #Hom(H,G) with the fractional edge covers of H in a very elegant and direct way. We will present a self-contained and simple proof of this result using Shearer’s inequality.
Read More