News
Diagrams, clustering, and coresets,and their application to the representation of polycrystals
Prof. Peter Gritzman
We study geometric diagrams and their relation to constrained clustering with a view towards representing and analyzing polycrystalline materials and their dynamics. We introduce various techniques for converting grain maps into geometric diagrams. In particular, weight-constrained anisotropic clustering allows to compute diagram representations from data on the volume, center and moments of the grains which are available through tomographic measurements. Also we develop new coreset techniques, interesting in their own right, which are utilized to significantly accelerate the computations. This effect is demonstrated on 3D real-world data sets.
(The talk is based on recent joint work with A. Alpers, M. Fiedler, F. Klemm.)
· 21.11.2023
· 17:00 - 18:00 Uhr
· HS 11, IM
A branch-and-bound algorithm for non-convex Nash equilibrium problems
Prof. Dr. Oliver Stein
We present the first spatial branch-and-bound method for the computation of the set of all epsilon-Nash equilibria of continuous box-constrained non-convex Nash equilibrium problems with an approximation guarantee. Thereby, the existence of epsilon-Nash equilibria is not assumed, but the algorithm is also able to detect their absence. After a brief introduction to branch-and-bound ideas in global optimization, we explain appropriate discarding and fathoming techniques for Nash equilibrium problems, formulate convergence results for the proposed algorithm, and report our computational experience.
Solving Mixed-Integer Semidefinite Programs
Prof. Dr. Marc Pfetsch
Semidefinite programs try to optimize a positive semidefinite matrix subject to linear inequality constraints. This class can be extended to mixed-integer semidefinite programs in which some of the variables are required to be integer. This forms an interesting class of optimization problems with many applications. This talk will introduce new methods as well as techniques that can be generalized from the linear to the semidefinite world. This includes presolving methods, e.g., fixing of variables, bound strengthening etc. Moreover, handling of symmetries and so-called conflict analysis can be adapted and have a positive impact on the performance. The impact of the methods will be illustrated computationally, using SCIP-SDP, an open-source solver for mixed-integer semidefinite programs based on SCIP.
Bicriteria Nash Flows over Time
Dr. Tim Oosterwijk
Flows over time are a natural way to incorporate flow dynamics that arise in various applications such as traffic networks. In this talk I will introduce a natural variant
of the deterministic fluid queuing model in which users aim to minimize their costs subject to arrival at their destination before a prespecified deadline. We determine
the existence and the structure of Nash flows over time and fully characterize the price of anarchy for this model.
The price of anarchy measures the ratio of the quality of the equilibrium and the quality of the optimum flow, where we evaluate the quality using two different natural
performance measures: the throughput for a given deadline and the makespan for a given amount of flow. While it turns out that both prices of anarchy can be unbounded
in general, we provide tight bounds for the important subclass of parallel path graphs.
Share this page
