Algoseminar

Download

algoseminar@lists.rwth-aachen.de

December 2024

1 participants
2 discussions

ADYN seminar
by Pandey, Sukanya 12 Dec '24

12 Dec '24

Dear all, Please find below the invitation from the DFG Research unit ADYN for their online seminar. Best, Sukanya -------- Forwarded Message -------- Subject: ADYN seminar: 16.12.24, 17:00 CET Date: Thu, 12 Dec 2024 10:08:18 +0100 From: koglin(a)cs.uni-frankfurt.de<mailto:koglin@cs.uni-frankfurt.de> To: adyn-talks(a)cs.uni-frankfurt.de<mailto:adyn-talks@cs.uni-frankfurt.de> Dear all, the DFG Research Unit ADYN invites you to their next online seminar session on * Monday, December 16th, 17:00 CET * Access via ZOOM: https://rwth.zoom-x.de/j/68837156442?pwd=H4OW7bUYYAMXSPiqvxXuEMuTTmk7VY.1 Meeting-ID: 688 3715 6442 Kenncode: 593098 The following talks will be given: (1) "A Strongly Polynomial Algorithm for The Minimum-Cost Generalized Flow Problem" by Lázló Végh (University of Bonn) (2) "Claims Trading with Default Costs" by Lars Huth (RWTH Aachen University) Abstracts: (1) We give a strongly polynomial algorithm for minimum cost generalized flow and, as a consequence, for all linear programs with at most two nonzero entries per row, or at most two nonzero entries per column. Our result can be viewed as progress towards understanding whether all linear programs can be solved in strongly polynomial time, also referred to as Smale's 9th problem. Our approach is based on the recent ‘subspace layered least squares’ interior point method, an earlier joint work with Allamigeon, Dadush, Loho and Natura. They show that the number of iterations needed by the IPM can be bounded in terms of the `straight line complexity’ of the central path. Roughly speaking, this is the minimum number of pieces of any piecewise linear curve that multiplicatively approximates the central path. Our main contribution is a combinatorial analysis showing that the straight-line complexity of any minimum cost generalised flow instance is polynomial in the number of arcs and vertices. This is joint work with Daniel Dadush, Zhuan Khye Koh, Bento Natura, and Neil Olver. (2) In the Eisenberg-Noe model, a model for debt between financial institutions and quantifying systemic risk, there are n banks represented by nodes in a directed graph. Directed edges represent debt claims, and edge weights are liabilities. Each bank can use incoming payments to clear its debt. Moreover, each bank has a non-negative amount of external assets, which can also be used for payment of claims. With this talk, I will convey basic intuitions for problems in the model, specifically claims trades. In claims trades, there is a bank v in distress and a trading partner w. The latter is taking over some claims of v and in return giving liquidity to v. The idea is to rescue v (or mitigate contagion effects from v’s insolvency). We focus on the impact of trading claims fractionally, i.e. when v and w can agree to trade only part of a claim. This is joint work with Martin Hoefer and Lisa Wilhelmi. For more information on ADYN and the seminar series, visit our website using the link https://adyn.informatik.rwth-aachen.de/ Best, Tim

1 0

Talk-Prof.Daniel Schmand
by Sukanya Pandey 05 Dec '24

05 Dec '24

Dear subscriber, We cordially invite you to the first talk of our group seminar. Please find the details below. *Date & Time: *Wednesday, 11th December at 14.00 hours *Location: *Seminar room I1 (Room 4017, E1) *Speaker: *Prof. Daniel Schmand *Topic: *"Solving Gerhard Woeginger's Hiking Problem" Best regards, Sukanya (on behalf of the Algorithms and Complexity Chair)

1 1