Noticias en español
Colour-bias perfect matchings in hypergraphs.
Abstract: We study conditions under which an r-edge-coloured k-uniform hypergraph has a perfect matching that contains substantially more than n/(kr) monochromatic edges. Our main result solves this problem for perfect matchings under minimum degree conditions, which answers recent questions of Gishboliner, Glock and Sgueglia. This is joint work with Hiêp Hàn, Richard Lang, João Pedro Marciano, Matías Pavez-Signé, Andrew Treglown, and Camila Zárate-Guerén.
Read MoreA strongly polynomial algorithm for the minimum-cost generalized flow problem.
Abstract: We give a strongly polynomial algorithm for minimum cost generalized flow, and hence for optimizing any linear program with at most two non-zero entries per row, or at most two non-zero entries per column. Our result can be viewed as progress towards understanding whether all linear programs can be solved in strongly polynomial time, also referred to as Smale’s 9th problem. Our approach is based on the recent primal-dual interior point method (IPM) due to Allamigeon, Dadush, Loho, Natura and Végh (FOCS ’22). They show that the number of iterations needed by the IPM can...
Read MoreOptimizing Throughput and Makespan of Queuing Systems by Information Design.
Abstract: We study the optimal provision of information for two natural performance measures of queuing systems: throughput and makespan. A set of parallel links (queues) is equipped with deterministic capacities and stochastic travel times where the latter depend on a realized scenario, and the number of scenarios is assumed to be constant. A continuum of flow particles (users) arrives at the system at a constant rate. A system operator knows the realization of the scenario and may (partially) reveal this information via a public signaling scheme to the flow particles. Upon arrival, the...
Read MoreBidding problems in European deregulated electricity markets.
Abstract: In this talk, we consider a bidding problem in European deregulated electricity markets. The goal of this problem is to maximize the profit of a Generation Company (GC) by choosing the best possible bids to propose to a Market Operator (MO) whose tasks is to minimize the daily price of electricity for the retailers. This problem has many challenging features to consider such as unit commitment for the GC, a market clearing system for the MO and demand and productions capacities are subject to increasing uncertainty due to renewable energies. Most studies in the literature try to...
Read MoreSet Selection with Uncertain Weights: Non-Adaptive Queries and Thresholds.
.Abstract: We study set selection problems where the weights are uncertain. Instead of its exact weight, only an uncertainty interval containing its true weight is available for each element. In some cases, some solutions are universally optimal; i.e., they are optimal for every weight that lies within the uncertainty intervals. However, it may be that no universally optimal solution exists, unless we are revealed additional information on the precise values of some elements. In the minimum cost admissible query problem, we are tasked to (non-adaptively) find a minimum-cost subset of...
Read MoreConstructions of circuits for the majority function.
Abstract: We will consider a task of computing the majority function by Boolean circuits. This function has logarithmic-depth circuits. Moreover, this remains true when circuits consist of just binary AND and OR, no negations. However, in this regime, no simultaneously explicit and “simple” construction is known (with “simple” being an informal property, referencing a subjective expositional complexity of a construction). In the talk, I will present a small piece of progress towards getting such a construction, and I will probably explain some classical constructions...
Read More