Package org.drip.sample.subarray

Class PolynomialTimeApproximateSubsetSum

java.lang.Object

org.drip.sample.subarray.PolynomialTimeApproximateSubsetSum

public class PolynomialTimeApproximateSubsetSum
extends java.lang.Object

PolynomialTimeApproximateSubsetSum illustrates the Approximate Sub-set Sum Check using a Polynomial Time Scheme. The References are:

• Bringmann, K. (2017): A near-linear Pseudo-polynomial Time Algorithm for Subset Sums Proceedings of the 28^th Annual ACM SIAM Symposium on Discrete Algorithms 1073-1084
• Horowitz, E., and S. Sahni (1974): Computing Partitions with Applications to the Knapsack Problem Journal of the ACM 21 (2) 277-292
• Kleinberg, J., and E. Tardos (2022): Algorithm Design 2^nd Edition Pearson
• Koiliaris, K., and C. Xu (2016): A Faster Pseudo-polynomial Time Algorithm for Subset Sum https://arxiv.org/abs/1507.02318 arXiV
• Wikipedia (2020): Subset Sum Problem https://en.wikipedia.org/wiki/Subset_sum_problem

• Module = Computational Core Module
• Library = Graph Algorithm Library
• Project = Graph Optimization and Tree Construction Algorithms
• Package = Sub-set Sum, k-Sum, and Maximum Sub-array Problems

Author:

Lakshmi Krishnamurthy

Constructor Summary

Constructors

Constructor	Description
PolynomialTimeApproximateSubsetSum()

Method Summary

Modifier and Type	Method	Description
static void	main(java.lang.String[] argumentArray)	Entry Point

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

PolynomialTimeApproximateSubsetSum

public PolynomialTimeApproximateSubsetSum()

Method Details

main

public static final void main(java.lang.String[] argumentArray)
                       throws java.lang.Exception

Entry Point

Parameters:

argumentArray - Command Line Argument Array

Throws:

java.lang.Exception - Thrown on Error/Exception Situation