Settlement fund circulation problem
Settlement fund circulation problem
复制标题
结算资金流转问题
DOI：
10.1016/j.dam.2019.03.017
复制
发表时间：
2019
影响因子：
1.1
通讯作者：
Hirotaka Ono and Yushi Uno
中科院分区：
文献类型：
--
作者：
Hitoshi Hayakawa;Toshimasa Ishii;Hirotaka Ono and Yushi Uno
在经济活动中，当银行缺乏清偿债务的资金时，中央银行具有支付银行款项的重要作用。为此，央行及时投放资金，使经济活动顺利进行。由于这一机制中的支付是按顺序处理的，央行投入的资金总额关键取决于支付的顺序。然后，利息进入准备支付顺序的金额，如果支付顺序可以由央行控制，或者如果它是在最坏的情况下确定的。这促使我们引入了一个全新的问题，我们称之为结算资金流通问题。问题表示如下：设G=(V，A)是一个有向多重图，有一个顶点集V和一个弧集A。每条弧∈A被赋予债务d(A)≥0，债务在一个弧数列π下按顺序清偿。将每个顶点v∈V放入序列下的pπ(V)≥0的量中。具有债务d：A→R+∪{0}的给定图G中的最小/最大结算资金流通问题(Min-Sfc/Max-Sfc)要求找到一个双射π：A→{1，2，…，|A|}最小化/最大化总资金∑v∈V pπ(V)。在这篇文章中，我们证明了Min-SFC和Max-SFC都是NP-难的，特别地，当G是(I)一个|V|=2的多重图或(Ii)一个树宽至多为2的简单图时，Min-SFC是(I)强NP-难的，而对于直径为4的简单树是(Ii)(不一定是强)NP-难的，而对于星是多项式时间可解的。同时，我们还给出了这两个问题的几种多项式时间可解情形。
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∈ A is endowed debt d (a)≥ 0, and the debts are settled sequentially under a sequence π of arcs. Each vertex v∈ V is put fund in the amount of p π (v)≥ 0 under the sequence. The minimum/maximum settlement fund circulation problem (Min-SFC/Max-SFC) in a given graph G with debts d: A→ R+∪{0} asks to find a bijection π: A→{1, 2,…,| A|} that minimizes/maximizes the total funds∑ v∈ V p π (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.