Noticias en español
Questions 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 MoreThe value of observability in dynamic pricing.
Abstract: Research on dynamic pricing has been growing during the last four decades due to its use in practice by a variety of companies as well as the several model variants that can be considered. In particular, we consider the pricing problem where a firm wants to sell one item to a single buyer in order to maximize expected revenues. On one hand, the firm commits to a price function over an infinite horizon. On the other, the buyer has a private value for the item and purchases at the time when his utility is maximized. In our model, the buyer is more impatient than the seller. When the...
Read MoreAn efficient symmetry breaking technique for arbitrary groups
Abstract: Symmetries are commonly found in Integer Linear Programs (ILPs) or in some of their substructures. Having many symmetric solutions could make common algorithms as branch-and-bound inefficient, hence breaking symmetries might yield important gains. Given a group of symmetries of an ILP, a Fundamental Domain is a set of R^n that aims to select a unique representative of symmetric vectors, i.e. such that each point in the set is a unique representative under its G-orbit, effectively breaking all symmetries of the group. The canonical Fundamental Domain found in the literature, which...
Read MoreOn the Price of Anarchy for Flows over Time
Abstract: Dynamic network flows, or network flows over time, constitute an important model for real-world situations where steady states are unusual, such as urban traffic and the Internet. In order to describe the temporal evolution of such systems one has to consider the propagation of flow across the network by tracking the position of each particle along time. These applications immediately raise the issue of analyzing dynamic network flows from a game-theoretic perspective. In this talk I will discuss dynamic equilibria in the deterministic fluid queuing model in single-source...
Read More