Noticias en español
Markov Decision Processes with long duration
Abstract: In a Markov Decision Process (MDP), at each stage, knowing the current state, the decision-maker chooses an action, and receives a reward depending on the current state of the world. Then a new state is randomly drawn from a distribution depending on the action and on the past state. Many optimal payoffs concepts have been introduced to analyze the strategic aspects of MDPs with long duration: asymptotic value, uniform value, liminf average payoff criterion… We provide sufficient conditions under which these concepts coincide, and discuss some open problems. (Joint work with Xavier...
Read MoreApproximating Vector Scheduling
Abstract: In this talk we will consider the Vector Scheduling problem, a natural generalization of the classical makespan minimization problem to multiple resources. Here, we are given n jobs, represented as d-dimensional vectors in [0,1]^d, and m identical machines, and the goal is to assign the jobs to machines such that the maximum load of each machine over all the coordinates is at most 1. For fixed d, the problem admits an approximation scheme, and the best known running time is n^{f(epsilon,d)}, where f(epsilon,d) = (1/epsilon)^{Õ(d)}, where Õ suppresses polylogarithmic terms in d. In...
Read MoreStructural-based Approach to Complexity of Optimization Algorithms
Abstract: The past few decades have witnessed tremendous progress in the field of Mathematical Optimization which led to a large proliferation of new optimization methods to many scientific fields. Among these is the field of machine learning whose applicability heavily relies on solvers which are capable of efficiently solving challenging large-scale optimization problems. Notwithstanding, we still lack an adequate complexity theory which satisfactorily quantifies the computational resources required for solving optimization problems of this nature. Motivated by the limitations of current...
Read MoreSUPERSET: A (super)natural variant of the card game SET
Abstract: We consider SUPERSET, a lesser-known but interesting variant of the famous card game SET. Here, players look for SUPERSETs instead of SETs, that is, the symmetric difference of two SETs that intersect in exactly one card. In this paper, we pose questions that have been previously posed for SET and provide answers to them; we also show relations between SET and SUPERSET. For the regular deck of cards, which can be identified with F_3^4, we give an elegant proof for the fact that the maximum number of cards that can be on the table without having a SUPERSET is 9, solving an open...
Read MoreThe long-term behaviour of a queue-based dynamic traffic model
Abstract: The fluid queueing model, introduced by Vickrey in ’69, is probably the simplest model that plausibly captures the notion of time-varying flows. Although the model is quite simple, our current theoretical understanding of equilibrium behaviour in this model is rather limited, and many fundamental questions remain open. I will discuss the resolution of a deceptively simple-sounding problem: do queue lengths remain bounded in the equilibria under natural necessary conditions? (Joint work with Roberto Cominetti and José Correa)
Read More