Seminars Quantitative Economics
MLSE Seminars
MLSE is a (mostly) bi-weekly seminar to foster cooperation between the Department of Microeconomics and Public Economics and the Department of Quantitative Economics. It aims to give researchers the opportunity to present their ongoing work and to facilitate cooperation
Operations Research Programme 2024
I4CS THREE INVITED TALKS
All colleagues from KE are invited to attend these talks. However, given the capacity of the rooms, there are limited seats.
Wednesday June 11 - 9:15-10:15 AM TS53 A0.23
Anna Wilbik - Maastricht University- "Responsibility and Explainability in Automated Systems"
Thursday June 12 -12:45-13:45 PM TS53 A.023
Klaus-Dieter Rest -University of Natural Resources and Life Sciences, Vienna- " Decision Support for Home Health Care Services in Urban Regions"
Friday June 13 - 11:30 AM -12:30 PM TS53 A.024
Rob van der Mei - CWI/VU Amsterdam- "Saving Lives with Mathematics: the Bumpy Road from Mathematical Modeling to a Successful Company"
Abstracts can be found on http://www.i4cs-conference.org/
Friday June 13 - 12:00 AM -13:30 PM TS53 H0.06
Whiteboard talk by Leo Krull - UM. - "Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time"
Abstract:
this work, we revisit the elementary scheduling problem $1||\sum p_j U_j$. The goal is to select, among $n$ jobs with processing times and due dates, a subset of jobs with maximum total processing time that can be scheduled in sequence without violating their due dates. This problem is NP-hard, but a classical algorithm by Lawler and Moore from the 60s solves this problem in pseudo-polynomial time $O(nP)$, where $P$ is the total processing time of all jobs. With the aim to develop best-possible pseudo-polynomial-time algorithms, a recent wave of results has improved Lawler and Moore's algorithm for $1||\sum p_j U_j$: First to time $\widetilde O(P^{7/4})$ [Bringmann, Fischer, Hermelin, Shabtay, Wellnitz; ICALP'20], then to time $\widetilde O(P^{5/3})$ [Klein, Polak, Rohwedder; SODA'23], and finally to time $\widetilde O(P^{7/5})$ [Schieber, Sitaraman; WADS'23]. It remained an exciting open question whether these works can be improved further.
In this work, we develop an algorithm in near-linear time $\widetilde O(P)$ for the $1||\sum p_j U_j$ problem. This running time not only significantly improves upon the previous results, but also matches conditional lower bounds based on the Strong Exponential Time Hypothesis or the Set Cover Hypothesis and is therefore likely optimal (up to subpolynomial factors). Our new algorithm also extends to the case of $m$ machines in time $\widetilde O(P^m)$. In contrast to the previous improvements, we take a different, more direct approach inspired by the recent reductions from Modular Subset Sum to dynamic string problems. We thereby arrive at a satisfyingly simple algorithm.
Joint work with Nick Fischer
Econometric Seminars Programme 2024
Thursday 20 June 2024 - 15.00 -16.00 PM TS53 room will follow
Speaker: Sumanta Basu - Cornell University
Abstract: info will follow
For previous seminars, please see our archive