License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.46
URN: urn:nbn:de:0030-drops-82351
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8235/
Go to the corresponding LIPIcs Volume Portal

Hayakawa, Hitoshi ; Ishii, Toshimasa ; Ono, Hirotaka ; Uno, Yushi

Settlement Fund Circulation Problem

pdf-format:
LIPIcs-ISAAC-2017-46.pdf (0.6 MB)

Abstract

In the economic activities,
the central bank has an important role to cover payments of banks,
when they are short of funds to clear their debts.
For this purpose, the central bank timely puts funds so that the economic activities go smooth.
Since payments in this mechanism are processed sequentially,
the total amount of funds put by the central bank critically
depends on the order of the payments.
Then an interest goes to the amount to prepare
if the order of the payments can be controlled by the central bank,
or if it is determined under the worst case scenario.
This motivates us to introduce a brand-new problem,
which we call the settlement fund circulation problem.
The problems are formulated as follows:
Let G=(V,A) be a directed multigraph with a vertex set V and an arc set A.
Each arc a\in A is endowed debt d(a)\ge 0,
and the debts are settled sequentially under a sequence \pi of arcs.
Each vertex v\in V is put fund in the amount of p_{\pi}(v)\ge 0
under the sequence.
The minimum/maximum settlement fund circulation problem (Min-SFC/Max-SFC)
in a given graph G with debts d: A\rightarrow \mathbb{R}_{+}\cup \{0\}
asks to find a bijection \pi:A\to \{1,2,\dots,|A|\}
that minimizes/maximizes the total funds \sum _{v\in V}p_{\pi }(v).
In this paper, we show that
both Min-SFC and Max-SFC are NP-hard;
in particular, Min-SFC is
(I) strongly NP-hard even if G is
(i) a multigraph with |V|=2 or (ii) a simple graph with treewidth at most two,and is (II) (not necessarily strongly) NP-hard for simple trees of diameter four,
while it is solvable in polynomial time for stars.
Also, we identify several polynomial time solvable cases for both problems.

BibTeX - Entry

@InProceedings{hayakawa_et_al:LIPIcs:2017:8235,
  author =	{Hitoshi Hayakawa and Toshimasa Ishii and Hirotaka Ono and Yushi Uno},
  title =	{{Settlement Fund Circulation Problem}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{46:1--46:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Yoshio Okamoto and Takeshi Tokuyama},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8235},
  URN =		{urn:nbn:de:0030-drops-82351},
  doi =		{10.4230/LIPIcs.ISAAC.2017.46},
  annote =	{Keywords: Fund settlement, Algorithm, Digraph, Scheduling}
}

Keywords: Fund settlement, Algorithm, Digraph, Scheduling
Collection: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Issue Date: 2017
Date of publication: 07.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI