Noticias en español
Generalized Assignment and Knapsack Problems in the Random-Order Model
Abstract: We study different online optimization problems in the random-order model. There is a finite set of bins with known capacity and a finite set of items arriving in a random order. Upon arrival of an item, its size and its value for each of the bins is revealed and it has to be decided immediately and irrevocably to which bin the item is assigned, or to not assign the item at all. In this setting, an algorithm is $\alpha$-competitive if the total value of all items assigned to the bins is at least an $\alpha$-fraction of the total value of an optimal assignment that knows all...
Read MoreExpansion of random 0/1 polytopes and the Mihail and Vazirani conjecture.
Abstract: A 0/1 polytope is the convex hull of a set of 0/1 d-dimensional vectors. A conjecture of Milena Mihail and Umesh Vazirani says that the graph of vertices and edges of every 0/1 polytope is highly connected. Specifically, it states that the edge expansion of the graph of every 0/1 polytope is at least one. Any lower bound on the edge expansion gives an upper bound for the mixing time of a random walk on the graph of the polytope. Such random walks are important because they can be used to generate an element from a set of combinatorial objects uniformly at random. A weaker form of...
Read MoreIdentifying the deviator.
Abstract: Alice and Bob control a random walk: alternately, each of them flips a fair coin, is supposed to report the outcome, and the random work advances according to the report. Suppose that the random walk did not return to the origin infinitely often. We suspect that one of Alice and Bob misreported the outcomes of her or his coin. Can we identify the deviator? More generally, several players are supposed to follow a prescribed profile of strategies (e,g, select each of Right and Left with probability 1/2). If they follow this profile, they will reach a given target (e.g., the...
Read MorePlanning Deeply Decarbonized Power Systems
Abstract: The energy transition is reshaping power system planning and operation as renewable penetration increases and electrification expands into sectors such as heating and cooling, making systems more dependent on weather-driven variability and uncertainty. Addressing these challenges requires models that can capture both short-term operational flexibility and long-term uncertainty, supported by suitable solution methods. This presentation examines the challenges of long-term power system planning under uncertainty in the context of the energy transition and explores the use of...
Read MoreOptimal d-Clique Decompositions for Hypergraphs.
Abstract: We determine the optimal constant for the Erdős-Pyber theorem on hypergraphs. Namely, we prove that every n-vertex d-uniform hypergraph H can be written as the union of a family F of complete d-partite hypergraphs such that every vertex of H belongs to at most (n choose d)/(n lg n) graphs in F. This improves on results of Csirmaz, Ligeti, and Tardos (2014), and answers an old question of Chung, Erdős, and Spencer (1983). Our proofs yield several algorithmic consequences, such as an O(n lg n) algorithm to find large balanced bicliques near the Kővári-Sós-Turán threshold. Moreover,...
Read MoreColumn Generation and the Feature Selection Problem.
Abstract: Column generation is a well-known decomposition method to solve linear and mixed integer problems with a large number of variables. A similar column generation decomposition method can be constructed for conic optimization problems. In this talk we present work that explores whether this can be a competitive solution method for the continuous relaxation of the feature selection problem.
Read More