Noticias en español
Finding 2-factors without triangles
Abstract: A 2-factor is a set of edges M of a graph G such that each vertex is incident to exactly two edges of M. Thus M determines a set of cycles in G. One can efficiently compute minimum cost 2-factors in weighted graphs. It is open whether one can do the same, if we forbid triangles, i.e., each cycle has at least four edges. For the unweighted case, a complicated result of Hartvigsen shows that one can find such a 2-matching in polynomial time. In the talk, we will review known results related to finding triangle free 2-factors, see its relation to the traveling salesman...
Read MoreSet-based Lagrangean decomposition methods for mathematical programming
Abstract: We present generic Lagrangean frameworks for primal (variable) and dual (constraint) decomposition algorithms for nonlinear mathematical programs with generalized inequalities. Akin to the Dantzig-Wolfe (DW) method and the Benders Decomposition (BD), we solve a succession of restricted problems/Lagrangean relaxations in a primal setting or relaxed problems/second stage problems in a dual standpoint. Our approach is generic in the sense that it takes as user-defined inputs 1) a structured subset of the primal (dual) feasibility set, and 2) a mechanism to update it at each...
Read MoreMaximizing Covered Area in a Euclidean Plane with Connectivity Constraint
Abstract: Given a set of unit disks in the plane and an integer K, the maximum area connected subset problem asks for a subset of K disks covering the maximum area, under the constraint that the area covered by the K disks is connected. This problem is motivated by wireless router deployment and is a special case of maximizing a submodular function under a connectivity constraint.
Read MoreFast Rates for Unbounded Losses: from ERM to Generalized Bayes
Abstract: I will present new excess risk bounds for randomized and deterministic estimators, discarding boundedness assumptions to handle general unbounded loss functions like log loss and squared loss under heavy tails. These bounds have a PAC-Bayesian flavor in both derivation and form, and their expression in terms of the information complexity forms a natural connection to generalized Bayesian estimators. The bounds hold with high probability and a fast $\tilde{O}(1/n)$ rate in parametric settings, under the recently introduced central’ condition (or various weakenings of this condition...
Read MoreProphet Secretary Through Blind Strategies
Abstract: In the classic prophet inequality, a problem in optimal stopping theory, samples from independent random variables arrive online. A gambler that knows the distributions, but cannot see the future, must decide at each point in time whether to stop and pick the current sample or to continue and lose that sample forever. The goal of the gambler is to maximize the expected value of what she picks and the performance measure is the worst case ratio between the expected value the gambler gets and what a prophet, that sees all the realizations in advance, gets. We study when the samples...
Read MoreA Linear Programming Based Approach to the Steiner Tree Problem with a Fixed Number of Terminals
Abstract: We present a set of integer programs (IPs) for the Steiner tree problem with the property that the best solution obtained by solving all, provides an optimal Steiner tree. Each IP is polynomial in the size of the underlying graph and our main result is that the linear programming (LP) relaxation of each IP is integral so that it can be solved as a linear program. However, the number of IPs grows exponentially with the number of terminals in the Steiner tree. As a consequence, we are able to solve the Steiner tree problem by solving a polynomial number of LPs, when the number of...
Read More