Marius Costandin

collaborators

4 papers

cs.CG2024

On a Geometric Interpretation Of the Subset Sum Problem

Marius Costandin

For $S \in N^{n}$ and $T \in N$ , the Subset Sum Problem (SSP) $\exists^{?} x \in {0, 1}^{n}$ such that $S^{T} \cdot x = T$ can be interpreted as the problem of deciding…

math.OC2024

A Deterministic Algorithm of Quasi-Polynomial Complexity for Clipped Cubes Volume Approximation

Marius Costandin

We give a deterministic method of quasi-polynomial complexity to approximate the volume of the intersection of the unit hypercube with two specific sets. The method can actually be…

cs.DS2024

Fully Subexponential Time Approximation Scheme for Product Partition

Marius Costandin

In this paper we study the Product Partition Problem (PPP), i.e. we are given a set of $n$ natural numbers represented on $m$ bits each and we are asked if a subset exists such tha…

math.CO2024

A Subexponential Reduction from Product Partition to Subset Sum

Marius Costandin

In this paper we study the Product Partition Problem (PPP), i.e. we are given a set of $n$ natural numbers represented on $m$ bits each and we are asked if a subset exists such tha…