DYNAMIC PROGRAMMING APPROACH TO THE COMPLETE SET PARTITIONING PROBLEM.

被引：0
|
作者：
Yeh, D.Yun [1 ]
机构：
[1] Arizona State Univ, Tempe, AZ, USA, Arizona State Univ, Tempe, AZ, USA
来源：
BIT (Copenhagen) | 1986年 / 26卷 / 04期
关键词：
MATHEMATICAL TECHNIQUES - Set Theory;
D O I：
暂无
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
The complete set partitioning (CSP) problem is a special case of the set partitioning problem where the coefficient matrix has 2**m minus 1 columns, each column being a binary representation of a unique integer between 1 and 2**m minus 1, m greater than equivalent to 1. It has wide applications in the area of corporate tax structuring in operations research. In this paper we propose a dynamic programming approach to solve the CSP problem, which has time complexity O(3**m), where n equals 2**m minus 1 is the size of the problem space.
引用
收藏
页码：467 / 474
相关论文
共 50 条
  • [41] Dynamic programming approach for solving the open shop problem
    Ansis Ozolins
    Central European Journal of Operations Research, 2021, 29 : 291 - 306
  • [42] A DYNAMIC PROGRAMMING APPROACH TO NONPARAMETRIC PROBLEM IN CALCULUS OF VARIATIONS
    BERKOVITZ, LD
    DREYFUS, SE
    JOURNAL OF MATHEMATICS AND MECHANICS, 1966, 15 (01): : 83 - +
  • [43] An iterative dynamic programming approach for the temporal knapsack problem
    Clautiaux, F.
    Detienne, B.
    Guillot, G.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2021, 293 (02) : 442 - 456
  • [44] A stochastic dynamic programming approach for the machine replacement problem
    Forootani, Ali
    Zarch, Majid Ghaniee
    Tipaldi, Massimo
    Iervolino, Raffaele
    ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE, 2023, 118
  • [45] A dynamic programming approach for the pipe network layout problem
    Shiono, Naoshi
    Suzuki, Hisatoshi
    Saruwatari, Yasufumi
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2019, 277 (01) : 52 - 61
  • [46] A dynamic programming approach to the impulse control synthesis problem
    Daryin, A. N.
    Kurzhanski, A. B.
    Seleznev, A. V.
    2005 44th IEEE Conference on Decision and Control & European Control Conference, Vols 1-8, 2005, : 8215 - 8220
  • [47] TRANSFORMATION OF SET PARTITIONING PROBLEM INTO A MAXIMUM WEIGHTED STABLE SET PROBLEM
    BILLIONNET, A
    RAIRO-RECHERCHE OPERATIONNELLE-OPERATIONS RESEARCH, 1978, 12 (03): : 319 - 323
  • [48] SOLUTION OF AN INTEGER-VALUED CONVEX PROGRAMMING PROBLEM.
    Perminov, O.N.
    Engineering Cybernetics (English translation of Tekhnicheskaya Kibernetika), 1973, 11 (04): : 561 - 565
  • [49] Dynamical programming in the partitioning optimization problem
    Chentsov, A.G.
    Chentsov, P.A.
    Avtomatika i Telemekhanika, 2002, (05): : 143 - 146
  • [50] CONVEX PROGRAMMING FORMULATIONS OF THE ASYMMETRIC TRAFFIC ASSIGNMENT PROBLEM.
    Hearn, Donald W.
    Lawphongpanich, Siriphong
    Nguyen, Sang
    1600, (18 B): : 4 - 5
12345