StefanWeltge

Events

Events Search and Views Navigation

Event Views Navigation

Today

  • Stefan Weltge, Integer programs with bounded subdeterminants and two nonzeros per row

    Room B232 IBS (기초과학연구원)

    We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain …

    Continue Reading

  • Stefan Weltge, The relaxation complexity of the standard simplex is logarithmic

    Room B332 IBS (기초과학연구원)

    For a set $X$ of integer points, the relaxation complexity $\operatorname{rc}(X)$ is the smallest number of facets of any polyhedron P whose integer points are precisely those of X. In this paper, we focus on the case where X is the discrete standard simplex $\Delta_d = \{0, e_1, ..., e_d\}$. We show that $\operatorname{rc}(\Delta_d) = …

    Continue Reading
DIMAG on YouTube

We use YouTube Live to broadcast seminar talks live if the speaker agrees.