Package org.drip.graph.subarray

Class PolynomialTimeApproximate

java.lang.Object

org.drip.graph.subarray.SubsetSum

org.drip.graph.subarray.PolynomialTimeApproximate

public class PolynomialTimeApproximate
extends SubsetSum

PolynomialTimeApproximate implements 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
PolynomialTimeApproximate(int[] numberArray, int target, double departureRatio)	PolynomialTimeApproximate Constructor

Method Summary

Modifier and Type	Method	Description
double	departureRatio()	Retrieve the Departure Ratio
boolean	targetSumExists()	Indicate if the Target Sum Match exists

Methods inherited from class org.drip.graph.subarray.SubsetSum

numberArray, target

Methods inherited from class java.lang.Object

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

Constructor Details

PolynomialTimeApproximate

public PolynomialTimeApproximate(int[] numberArray,
int target,
double departureRatio)
                          throws java.lang.Exception

PolynomialTimeApproximate Constructor

Parameters:

numberArray - The Input Number Array

target - The Sum Target

departureRatio - The Departure Ratio

Throws:

java.lang.Exception - Thrown if the Inputs are Invalid

Method Details

departureRatio

public double departureRatio()

Retrieve the Departure Ratio

Returns:

The Departure Ratio

targetSumExists

public boolean targetSumExists()

Description copied from class: SubsetSum

Indicate if the Target Sum Match exists

Specified by:

targetSumExists in class SubsetSum

Returns:

TRUE - The Target Sum Match exists