Noticias en español
Online assortment optimization for two-sided matching platforms.
Abstract: Motivated by online labor markets, we consider the online assortment optimization problem faced by a two-sided matching platform that hosts a set of suppliers waiting to match with a customer. Arriving customers are shown an assortment of suppliers, and may choose to issue a match request to one of them. Before leaving the platform, each supplier reviews all the match requests he has received, and based on his preferences, he chooses whether to match with a customer or to leave unmatched. We study how platforms should design online assortment algorithms to maximize the expected...
Read MoreA Tight (3/2+ε)-Approximation for Skewed Strip Packing.
Abstract: In the Strip Packing problem, we are given a vertical half-strip [0,W] × [0,+∞) and a collection of open rectangles of width at most W. Our goal is to find an axis-aligned (non-overlapping) packing of such rectangles into the strip such that the maximum height OPT spanned by the packing is as small as possible. Strip Packing generalizes classical well-studied problems such as Makespan Minimization on identical machines (when rectangle widths are identical) and Bin Packing (when rectangle heights are identical). It has applications in manufacturing, scheduling and energy consumption...
Read MoreStability of Stochastic Gradient Descent on Nonsmooth Convex Losses.
Abstract: Uniform stability is a notion of algorithmic stability that bounds the worst case change in the model output by the algorithm when a single data point in the dataset is replaced. An influential work of Hardt, Recht & Singer (ICML’16) provides strong upper bounds on the uniform stability of the stochastic gradient descent (SGD) algorithm on sufficiently smooth convex losses. These results led to important progress in understanding of the generalization properties of SGD and several applications to differentially private convex optimization for smooth losses. Our work is...
Read MoreRumor Spreading in Random Hyperbolic Graphs.
Abstract: We analyze several variants of the following randomized broadcast algorithm (a.k.a.~rumor spreading process) on Random Hyperbolic Graphs (RHG). At the beginning, only one node from the giant component (largest connected component) of the RHG is informed. Then, in each round, each informed node chooses a neighbor uniformly and independently at random and pushes the information to it. We give precise estimates (in terms of the RHG’s parameters) for the number of steps this algorithm takes to inform every node in the giant component of the RHG. Our estimates hold with high...
Read MoreMaximal Quadratic-Free Sets.
Abstract: The intersection cut paradigm is a powerful framework that facilitates the generation of valid linear inequalities, or cutting planes, for a potentially complex feasible set S of an optimization problem. The key ingredient in this construction is an S-free set: a convex zone whose interior does not intersect S. Ideally, such S-free set would be maximal inclusion-wise, as it would generate a deeper cutting plane. In the case of integer programming, maximal lattice-free sets (i.e., when S corresponds to the integer lattice) have proven to be a powerful tool and have been carefully...
Read MoreOnline Algorithms with Machine Learned Advice.
Abstract: Machine-learned predictors, although achieving very good results for inputs resembling training data, cannot possibly provide perfect predictions in all situations. Still, decision-making systems that are based on such predictors need not only to benefit from good predictions but also to achieve a decent performance when the predictions are inadequate. Assume that you are given some (machine-learned) information regarding an online problem. It would be desirable to design an online algorithm that incorporates this information in order to on one hand obtain an improved...
Read More