Optimization Seminar

Modal title

Modal content

Autumn Semester 2017

Date / Time

Speaker

Title

Location

25 September 2017
16:30-17:30

Dr. Timm Oertel
Cardiff University, Cardiff, United Kingdom

Event Details

Optimization Seminar

Title	Sparse solutions of linear Diophantine systems
Speaker, Affiliation	Dr. Timm Oertel, Cardiff University, Cardiff, United Kingdom
Date, Time	25 September 2017, 16:30-17:30
Location	HG G 19.1
Abstract	We present structural results on solutions to linear Diophantine systems with the smallest number of non-zero entries. Our tools are algebraic and number theoretic in nature and include Siegel’s Lemma, generating functions, and commutative algebra. These results have some interesting consequences in discrete optimization.

Sparse solutions of linear Diophantine systemsread_more

HG G 19.1

6 November 2017
16:30-17:30

Dr. Christos Kalaitzis
ETH Zurich, Switzerland

Event Details

Optimization Seminar

Title	An Improved Approximation Algorithm for the Tree Augmentation Problem
Speaker, Affiliation	Dr. Christos Kalaitzis, ETH Zurich, Switzerland
Date, Time	6 November 2017, 16:30-17:30
Location	HG G 19.1
Abstract	The Tree Augmentation Problem (TAP) is a fundamental network design problem in which we are given a tree and a set of additional edges, also called links. The task is to find a set of links, of minimum size, whose insertion into the tree leads to a 2-edge-connected graph. The best known approximation algorithm for the problem achieves a ratio of 1.5. In this talk, I will present an algorithm that achieves an 1.458-approximation ratio, thus establishing that it is possible to improve upon the 1.5 factor. The result is based on two major components. The first one is a black-box reduction that shows how, given an approximation algorithm for a specific class of instances (which we call wide trees), one can achieve the same approximation guarantee for the unweighted TAP problem. The second component is an algorithm that achieves an approximation ratio of 1.458 for wide trees. This talk is based on joint work with Fabrizio Grandoni and Rico Zenklusen.

An Improved Approximation Algorithm for the Tree Augmentation Problemread_more

HG G 19.1

28 November 2017
15:00-16:00

Simon Bruggmann
ETH Zurich, Switzerland

Event Details

Optimization Seminar

Title	Submodular Maximization through the Lens of Linear Programming
Speaker, Affiliation	Simon Bruggmann, ETH Zurich, Switzerland
Date, Time	28 November 2017, 15:00-16:00
Location	HG G 19.2
Abstract	The simplex algorithm for linear programming is based on the fact that any local optimum with respect to the polyhedral neighborhood is also a global optimum. We show that a similar result carries over to submodular maximization. In particular, every local optimum of a constrained monotone submodular maximization problem yields a 1/2-approximation, and we also present an appropriate extension to the non-monotone setting. Moreover, we describe a very general local search procedure that applies to a wide range of constraint families, and unifies as well as extends previous methods. In our framework, we match known approximation guarantees while disentangling and simplifying previous approaches. Moreover, despite its generality, we are able to show that our local search procedure is slightly faster than previous specialized methods. Furthermore, we negatively answer the open question whether a linear optimization oracle may be enough to obtain strong approximation algorithms for submodular maximization. We do this by providing an example of a constraint family on a ground set of size n for which, if only given a linear optimization oracle, any algorithm for submodular maximization with a polynomial number of calls to the linear optimization oracle has an approximation ratio of only O(log n/(n^{0.5} loglog n)). This is joint work with Rico Zenklusen.

Submodular Maximization through the Lens of Linear Programmingread_more

HG G 19.2

4 December 2017
16:30-17:30

Ingo Stallknecht
University of Heidelberg, Germany

Event Details

Optimization Seminar

Title	Polynomial integer programming as projection
Speaker, Affiliation	Ingo Stallknecht, University of Heidelberg, Germany
Date, Time	4 December 2017, 16:30-17:30
Location	HG G 19.2
Abstract	We generalise Fourier-Motzkin elimination to polynomial integer programming. This leads to algorithms for eliminating real-valued respectively integer-valued variables for polynomial mixed-integer programming problems. For this purpose, we briefly present polyhedral projection as well as a relatively new projection algorithm for integer programming by Williams and Hooker. Afterwards we derive our main results in the polynomial case and demonstrate these by an example. As an application, we regard MILP-representable sets and their algebraic characterization through Chvátal-inequalities. Our theory may be used for generalising these findings to the polynomial case.

Polynomial integer programming as projectionread_more

HG G 19.2

Note: if you want you can subscribe to the iCal/ics Calender.

Archive: SS 22 SS 20 AS 19 SS 19 AS 18 SS 18 AS 17 SS 17 AS 16 SS 16 AS 15 SS 15 AS 14 SS 14 AS 13 SS 13 AS 12 SS 12 AS 11 SS 11 AS 10 SS 10 AS 09