Seminars Quantitative Economics

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

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

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

For previous workshops, please see our archive