A new method for showing nonexistence of solutions for a generalized Brezis-Nirenberg problem

Event Date: Oct 08, 2018 in AGCO, Seminars

Abstract:   In this talk I will present new results on the nonexistence of solutions for a generalized hyperbolic Brezis-Nirenberg problem.  Here we combine a classical Pohozaev argument with a generalized Hardy inequality.   This is joint work with Soledad Benguria (U. Wisconsin).  

Read More

A Median-Type Condition for Graph Tiling

Event Date: Sep 26, 2018 in AGCO, Seminars

Abstract:   Komlos determined the asymptotically optimal minimum degree condition for covering a given proportion of vertices of a host graph by vertex-disjoint copies of a fixed graph H. We show that the minimum degree condition can be relaxed in the sense that we require only a given fraction of vertices to have the prescribed degree. Joint work with Diana Piguet.  

Read More

Extension Complexity.

Event Date: Sep 12, 2018 in AGCO, Seminars

Abstract: A polytope Q is called an extension of a polytope P if P is a projection of Q. The extension complexity of a polytope is the minimum number of inequalities needed to describe any of its extensions. In this talk I will describe some results related to extension complexities of several important polytopes arising in combinatorial optimization and discuss how extension complexity can be used to model computational difficulty of solving problems.

Read More

Strong Algorithms for the Ordinal Matroid Secretary Problem

Event Date: Sep 05, 2018 in AGCO, Seminars

Abstract: A general technique and analysis for the matroid secretary problem is presented and then we show how to achieve a 4-competitive algorithm for the case of graphic matroids.

Read More

A (5/3 + ε)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes

Event Date: Aug 29, 2018 in AGCO, Seminars

Abstract:  In the unsplittable flow on a path problem (UFP) we are given a path with edge capacities and a collection of tasks. Each task is characterized by a subpath, a profit, and a demand. Our goal is to compute a maximum profit subset of tasks such that, for each edge e, the total demand of selected tasks that use e does not exceed the capacity of e. The current best polynomial-time approximation factor for this problem is 2 + eps for any constant eps>0. This is the best known factor even in the case of uniform edge capacities. These results, likewise most prior work, are based on a...

Read More

MST en grafos con incertidumbre y cómo encontrarlos con consultas de mínimo costo.

Event Date: Aug 22, 2018 in AGCO, Seminars

Abstract: En esta presentación estudiaremos el problema de MST en un contexto donde los pesos son inciertos. Dado un grafo, para cada arista se conocerá un conjunto no vacío que contiene los posibles pesos de la arista. Eventualmente los verdaderos pesos se darán a conocer y llamamos a esto una realización de los pesos. Los algoritmos a considerar tendrán acceso a una operación especial llamada “consulta” que revela de manera inmediata el verdadero peso de una arista a cierto costo predeterminado. Nos enfocaremos en los siguientes problemas: – El problema de MST uniforme;...

Read More