# AGCO

## Finding 2-factors without triangles

Event Date: Apr 17, 2019 in AGCO, Seminars

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...

## Set-based Lagrangean decomposition methods for mathematical programming

Event Date: Apr 10, 2019 in AGCO, Seminars

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...

## Maximizing Covered Area in a Euclidean Plane with Connectivity Constraint

Event Date: Mar 20, 2019 in AGCO, Seminars

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.

## Fast Rates for Unbounded Losses: from ERM to Generalized Bayes

Event Date: Nov 14, 2018 in AGCO, Seminars

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...

## Prophet Secretary Through Blind Strategies

Event Date: Nov 28, 2018 in AGCO, Seminars

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...