Noticias en español
A 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 MoreConvergence Analysis of Davis-Yin Splitting via Scaled Relative Graphs.
Abstract: Davis-Yin splitting (DYS) has found a wide range of applications in optimization, but its linear rates of convergence have not been studied extensively. The scaled relative graph (SRG) simplifies the convergence analysis of operator splitting methods by mapping the action of the operator onto the complex plane, but the prior SRG theory did not fully apply to the DYS operator. In this work, we formalize an SRG theory for the DYS operator and use it to obtain tighter contraction factors.
Read More