sign in
TUM – TUM – Menü

Research Seminar

The M9 Research Seminar is a weekly seminar in which our guests as well as our group discuss recent research advances and interesting open problems in applied geometry and discrete mathematics.

Usual time: Monday 15:15

Usual room: 02.04.011

Past and Upcoming Talks

Date Speaker Title
Jul 18, 2016, 14:15 Rajan Udwani (MIT) Robust Monotone Submodular Function Maximization
Jul 15, 2016, 16:00 Egon Schulte (Northeastern University, Boston) Polyhedral Complexes and Graphs for Crystallographic Groups
Jul 04, 2016, 15:15 Yuan Zhou (UC Davis) Toward computer-assisted discovery and automated proofs of cutting plane theorems
Jun 27, 2016, 14:15 Sesh Kumar (INRIA) Learning bounded treewidth decomposable graphs to maximize submodular functions
Jun 20, 2016, 15:15 Maciej Drwal (Wrocław) Algorithms for selected robust scheduling problems with interval data

Abstracts

Rajan Udwani (MIT): Robust Monotone Submodular Function Maximization

We consider a robust formulation, introduced by Krause et al. (2008), of the classical cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results. The robustness considered is w.r.t. adversarial removal of up to tau elements from the chosen set. For the fundamental case of tau = 1, we give a deterministic (1-1/e)-Omega(1/m) approximation, which makes O(n^{m+1}) queries. In the process, we develop a deterministic (1-1/e)-Omega(1/m) approximate greedy algorithm for bi-objective maximization of monotone submodular functions.

Generalizing the ideas and using a result from Chekuri et al. (2010), we show a randomized (1-1/e)-epsilon approximation for constant tau. For tau = o(sqrt{k}), we give a fast and practical 0.387 algorithm. Finally, we also give a black box result for the more general setting of robust maximization of monotone submodular functions subject to an independence system.

This is joint work with James B. Orlin and Andreas S. Schulz.

Host: Andreas S. Schulz

Egon Schulte (Northeastern University, Boston): Polyhedral Complexes and Graphs for Crystallographic Groups

The study of highly symmetric discrete structures in ordinary 3-space has a long and fascinating history. A radically new, skeletal approach to polyhedra was pioneered by Grunbaum in the 1970's, building on Coxeter's work. A polyhedron, or more general polyhedral structure, is viewed as a finite or infinite periodic geometric edge graph in space equipped with additional (super) structure imposed by the faces, and its symmetry is measured by transitivity properties of its geometric symmetry group. Since the mid 1970's, there has been a lot of activity in this area. We survey the present state of the ongoing program to classify discrete polyhedral structures in space by distinguished transitivity properties of their symmetry groups.

Yuan Zhou (UC Davis): Toward computer-assisted discovery and automated proofs of cutting plane theorems

Inspired by the breakthroughs of the polyhedral method for combinatorial optimization in the 1980s, generations of researchers have studied the facet structure of convex hulls to develop strong cutting planes. We ask how much of this process can be automated: In particular, can we use algorithms to discover and prove theorems about cutting planes? We focus on general integer and mixed integer programming, and use the framework of cut-generating functions. Using a metaprogramming technique followed by practical computations with semialgebraic cell complexes, we provide computer-based proofs for old and new cutting-plane theorems in Gomory-Johnson's model of cut generating functions.

Sesh Kumar (INRIA): Learning bounded treewidth decomposable graphs to maximize submodular functions

Title: Learning bounded treewidth decomposable graphs to maximize submodular functions.

Abstract: We consider the problem of learning the structure of undirected graphical models with bounded treewidth, within the maximum likelihood framework. This is an NP-hard problem and most approaches consider local search techniques. In this work, we pose it as a combinatorial optimization problem, which is then relaxed to a convex optimization problem that involves searching over the forest and hyperforest polytopes with special structures. A supergradient method is used to solve the dual problem, with a run-time complexity of O(k^3 n^{k+2} log n) for each iteration, where n is the number of variables and k is a bound on the treewidth.

We now consider the problem of maximizing submodular functions; while this problem is known to be NP-hard, several numerically efficient local search techniques with approximation guarantees are available. In this work, we propose a novel convex relaxation which is based on the relationship between submodular functions, entropies and probabilistic graphical models.

In a graphical model, the entropy of the joint distribution decomposes as a sum of marginal entropies of subsets of variables; moreover, for any distribution, the entropy of the closest distribution factorizing in the graphical model provides an bound on the entropy. For directed graphical models, this is a direct consequence of the submodularity of the entropy function, and allows the generalization of graphical-model-based upper bounds to any submodular functions. This notion can also be used to define undirected graphical model based bounds. These upper bounds may then be jointly maximized with respect to a set, while minimized with respect to the graph, leading to a convex variational inference scheme for maximizing submodular functions, based on outer approximations of the marginal polytope and maximum likelihood bounded treewidth structures. By considering graphs of increasing treewidths, we may then explore the trade-off between computational complexity and tightness of the relaxation. We also present extensions to constrained problems and maximizing the difference of submodular functions, which include all possible set functions.

Host: Andreas S. Schulz

Maciej Drwal (Wrocław): Algorithms for selected robust scheduling problems with interval data

Maciej Drwal (Wrocław University of Technology)

Title: Algorithms for selected robust scheduling problems with interval data

Abstract: We consider basic scheduling problems under the assumption that input data parameters are not given precisely, and their probability distributions are not known. We apply the concept of maximum regret to define the notion of robust solution. Efficiency of algorithms for computing the maximum regret, and algorithms for minimizing it, are considered. We show that robust version of multiprocessor scheduling problem to minimize the total completion time is strongly NP-hard. For the single machine sequencing to minimize the weighted number of late jobs we show special cases that are solvable in polynomial time, as well as the ones that are hard. The presentation is concluded with general comments regarding min-max regret approach to discrete optimization.

Host: Nicole Megow

Research Unit M9


Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

Prof. Dr. Stefan Weltge
Discrete Mathematics

News

Jan 25th, 2019
Case Studies 2019: Preliminary Meeting on Wed, Feb 6th, at 16:00 in room MI 03.06.011.