On a Geometric Interpretation Of the Subset Sum Problem
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929568389005312 |
|---|---|
| author | Costandin, Marius |
| author_facet | Costandin, Marius |
| contents | For $S \in \mathbb{N}^n$ and $T \in \mathbb{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 whether the intersection of the positive unit hypercube $Q_n = [0,1]^n$ with the hyperplane $S^T\cdot \left(x - \frac{S}{\|S\|^2 }\cdot T \right) = 0$ contains at least a vertex. In this paper, we give an algorithm of complexity $\mathcal{O}\left( \frac{1}ε\cdot n^b \right)$, for some absolute constant $b$, which either proves that there are no vertices in a slab of thickness $ε$ either finds a vertex in the slab of thickness $4\cdot ε$. It is shown that any vertex $P$ in a slab of thickness $ε$ meets $\left| \frac{S^T\cdot P}{T} - 1 \right| \leq ε$, therefore making the proposed algorithm a FPTAS for the SSP. The results are then applied to the study of the so called Simultaneous Subset-Sum Problem (SSSP). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_19024 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On a Geometric Interpretation Of the Subset Sum Problem Costandin, Marius Computational Geometry Optimization and Control For $S \in \mathbb{N}^n$ and $T \in \mathbb{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 whether the intersection of the positive unit hypercube $Q_n = [0,1]^n$ with the hyperplane $S^T\cdot \left(x - \frac{S}{\|S\|^2 }\cdot T \right) = 0$ contains at least a vertex. In this paper, we give an algorithm of complexity $\mathcal{O}\left( \frac{1}ε\cdot n^b \right)$, for some absolute constant $b$, which either proves that there are no vertices in a slab of thickness $ε$ either finds a vertex in the slab of thickness $4\cdot ε$. It is shown that any vertex $P$ in a slab of thickness $ε$ meets $\left| \frac{S^T\cdot P}{T} - 1 \right| \leq ε$, therefore making the proposed algorithm a FPTAS for the SSP. The results are then applied to the study of the so called Simultaneous Subset-Sum Problem (SSSP). |
| title | On a Geometric Interpretation Of the Subset Sum Problem |
| topic | Computational Geometry Optimization and Control |
| url | https://arxiv.org/abs/2410.19024 |