Noticias en español
Rumor 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 MoreQuestions on finite metric spaces that arise in the euclidean plane.
Abstract: In this talk we will discuss some recent results about the following conjecture of Xiaomin Chen and Vasek Chvátal: In each finite metric space with n points there are at least n different lines or there is a line containing all the points.
Read MoreThe Two-Sided Game of Googol and Sample-Based Prophet Inequalities.
Abstract: The secretary problem or the game of Googol are classic models for online selection problems that have received significant attention in the last five decades. In this paper, we consider a variant of the problem and explore its connections to data-driven online selection. Specifically, we are given n cards with arbitrary non-negative numbers written on both sides. The cards are randomly placed on n consecutive positions on a table, and for each card, the visible side is also selected at random. The player sees the visible side of all cards and wants to select the card with the...
Read MoreA Water-Filling Primal-Dual Algorithm for Approximating Non-Linear Covering Problems.
Abstract: Obtaining strong linear relaxations of capacitated covering problems constitute a significant technical challenge even for simple settings. For one of the most basic cases, the Knapsack-Cover (Min-Knapsack) problem, the relaxation based on knapsack-cover inequalities has an integrality gap of 2. These inequalities are exploited in more general problems, many of which admit primal-dual approximation algorithms. Inspired by problems from power and transport systems, we introduce a general setting in which items can be taken fractionally to cover a given demand. The cost incurred by...
Read More