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 条
  • [1] A DYNAMIC-PROGRAMMING APPROACH TO THE COMPLETE SET PARTITIONING PROBLEM
    YEH, DY
    BIT, 1986, 26 (04): : 467 - 474
  • [2] MICROCOMPUTER PROGRAM FOR THE SET PARTITIONING PROBLEM.
    Ram, Balasubramanian
    Al-Najjar, Mazen
    CoED (Journal) (Computers in Education Division of ASEE), 1986, 6 (03): : 7 - 8
  • [3] Transformation of the Set Partitioning Problem Into a Maximum Weighted Stable Set Problem.
    Billionnet, Alain
    RAIRO Recherche Operationnelle, 1978, (03): : 319 - 323
  • [4] Dynamic Programming Approach for Solving Rectangle Partitioning Problem
    Yendri, Sheinna
    Soelaiman, Rully
    Yuhana, Umi Laili
    Yendri, Sheilla
    IAENG International Journal of Computer Science, 2022, 49 (02):
  • [5] ALGORITHM FOR COMPLETE SET PARTITIONING PROBLEM
    SALKIN, HM
    LIN, CH
    OPERATIONS RESEARCH, 1975, 23 : B389 - B389
  • [6] SET PARTITIONING BASED HEURISTIC FOR POWER NETWORK DEVELOPMENT PROBLEM.
    Ocieczek, Grzegorz
    1600, (03):
  • [7] Partitioning a finite set by a dynamic programming method
    Chentsov, AG
    Chentsov, PA
    AUTOMATION AND REMOTE CONTROL, 2000, 61 (04) : 658 - 670
  • [8] AN EFFICIENT ALGORITHM FOR THE COMPLETE SET PARTITIONING PROBLEM
    LIN, CHM
    SALKIN, HM
    DISCRETE APPLIED MATHEMATICS, 1983, 6 (02) : 149 - 156
  • [9] NOTE ON A TWO-DIMENSIONAL DYNAMIC PROGRAMMING PROBLEM.
    Page, E.
    Operational Research Quarterly, 1975, 26 (2 i): : 321 - 324
  • [10] A set partitioning approach to the crew scheduling problem
    Mingozzi, A
    Boschetti, MA
    Ricciardelli, S
    Bianco, L
    OPERATIONS RESEARCH, 1999, 47 (06) : 873 - 888
12345