Noticias en español
Parametric Polyhedra in Mixed-Integer Programming.
Abstract: We present some old and new results on arbitrary families of parametric polyhedra. First, if the constraint matrix is fixed, in the literature there are structural results for the integer hull and the finiteness of cutting plane closures for varying r.h.s. For instance, recently, Becu et al. proved in “Approximating the Gomory Mixed-Integer Cut Closure Using Historical Data” that the GMI closure of this family is finitely generated, in the sense that there exists a finite list of aggregation weights defining the GMI cuts that give the GMI closure for any polyhedra in...
Read MoreMathematical Optimization Models for the Euclidean Steiner Tree Problem in R^n.
Abstract: In this talk, we review the mathematical optimization models for the Euclidean Steiner Tree Problem (ESTP) in n dimensions proposed in the literature. The development of such models for the ESTP began in the late 1990s. The ESTP is a mixed integer nonlinear optimization problem with a history dating back to the 17th century. Several properties of its optimal solutions are well known, but it is still a big challenge to encode these properties in its modeling, aiming for its numerical resolution with branch-and-bound algorithms. We identify some of the difficulties and present the...
Read MoreThe Rawlsian Prophet: Max-Min Fair Online Allocation.
Abstract: Prophet inequalities are a central framework in online stochastic decision making, comparing online algorithms to an omniscient benchmark. The utilitarian objective of maximizing expected total value is well understood, with tight competitive ratios across full-information, sample-based, and combinatorial settings. We study prophet inequalities under Rawlsian max-min fairness objectives, and distinguish between two natural notions of fairness: ex-ante and ex-post. The former aims to maximize the minimum expected value, while the latter seeks to maximize the expected minimum value....
Read MoreHiring under uncertainty and competition: variations of the secretary problema.
Abstract: In this talk, we study some variations of the Secretary Problem. In the Secretary Problem, an employer sees a sequence of candidates. Each time a new candidate arrives, the employer makes an irrevocable choice on whether to hire based only on the relative ranking of the candidates seen so far. The employer tries to maximize the probability of hiring the best. It is known that the optimal strategy hires the best with probability 1/e. We consider an infinite arrival regime. This allows us to apply a lemma characterizing the number of “promising candidates” in any given time interval....
Read MoreBeating Greedy Asymptotically for Weighted k-Matroid Intersection
Abstract: Greedy is one of the most widely used algorithmic paradigms, both in practice and in theory. Its success is classically explained by matroid theory: whenever the underlying optimization problem has a matroid structure, Greedy is optimal. Greedy also extends to problems involving multiple matroids, but its performance guarantee deteriorates to 1/k, where k is the number of matroids. For Weighted k-Matroid Intersection, Greedy has long been the asymptotically best-known algorithm. In this talk, I will survey recent progress that improves on Greedy for Weighted k-Matroid Intersection...
Read MoreDecremental tree sums.
Abstract: In this talk, I will discuss the following semi-dynamic graph problem: Maintain a vertex-weighted forest under the following operations: Delete an edge; change the weight of a vertex; and, given a vertex v, return the total weight of all vertices in the same tree as v. I’ll present the following results from joint work with Marek Sokołowski. * A data structure with O(m + n log* n) time for m operations; * a linear-time data structure for *unweighted* forests; * and a data structure with (conditionally) optimal, but unknown running time. At the end, I will briefly speculate...
Read More