Dr Tom Friedetzky tom.friedetzky@durham.ac.uk
Associate Professor
Dr Tom Friedetzky tom.friedetzky@durham.ac.uk
Associate Professor
D. Kutner
Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
Professor Iain Stewart i.a.stewart@durham.ac.uk
Professor
Dr Amitabh Trehan amitabh.trehan@durham.ac.uk
Associate Professor
The networks-based study of financial systems has received considerable attention in recent years, but seldom explicitly incorporated the dynamic aspects of such systems. We consider this problem setting from the temporal point of view, and we introduce the Interval Debt Model (IDM) and some scheduling problems based on it, namely: Bankruptcy Minimization / Maximization, in which the aim is to produce a schedule with at most / at least k bankruptcies; Perfect Scheduling, the special case of the minimization variant where k=0; and Bailout Minimization, in which a financial authority must allocate a smallest possible bailout package to enable a perfect schedule. In this paper we investigate the complexity landscape of the various variants of these problems. We show that each of them is NP-complete, in many cases even on very restrictive input instances. On the positive side, we provide for Perfect Scheduling a polynomial-time algorithm on (rooted) out-trees. In wide contrast, we prove that this problem is NP-complete on directed acyclic graphs (DAGs), as well as on instances with a constant number of nodes (and hence also constant treewidth). When the problem definition is relaxed to allow fractional payments, we show by a linear programming argument that Bailout Minimization can be solved in polynomial time.
Friedetzky, T., Kutner, D., Mertzios, G., Stewart, I., & Trehan, A. (2023, January). Payment scheduling in the Interval Debt Model. Presented at 48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2023), Novy Smokovec, Slovakia
Presentation Conference Type | Conference Paper (published) |
---|---|
Conference Name | 48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2023) |
Start Date | Jan 15, 2023 |
End Date | Jan 19, 2023 |
Acceptance Date | Sep 30, 2022 |
Online Publication Date | Jan 1, 2023 |
Publication Date | 2023-01 |
Deposit Date | Oct 19, 2022 |
Publicly Available Date | Oct 20, 2022 |
Print ISSN | 0302-9743 |
Publisher | Springer Verlag |
Pages | 267-282 |
Series Title | Lecture Notes in Computer Science |
Series ISSN | 0302-9743 |
ISBN | 9783031231001 |
DOI | https://doi.org/10.1007/978-3-031-23101-8_18 |
Public URL | https://durham-repository.worktribe.com/output/1135863 |
Accepted Conference Proceeding
(521 Kb)
PDF
Randomized renaming in shared memory systems
(2021)
Journal Article
Time-space trade-offs in population protocols for the majority problem
(2020)
Journal Article
Self-Stabilizing Balls and Bins in Batches
(2018)
Journal Article
Threshold Load Balancing With Weighted Tasks
(2017)
Journal Article
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2025
Advanced Search