Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 10 of 10 for “"Subset Sum"”.
-
Pigeonhole Equal Subset Sum in O ⃰ (2ⁿ/³)
Subset Sum is a well known NP-hard problem. In Subset Sum, we are given a set of n integers S = {a1,··· ,an} and a target integer t, and are asked to find a subset A ⊆ [n] such that [formula]. We study a variant of the Subset Sum problem, Pigeonhole Equal Subset Sum. In Pigeonhole Equal Subset Sum, …
-
Basis reduction algorithms and subset sum problems
Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1991.
-
Algorithms for Subset Sum using linear sketching
Given n positive integers, the Modular Subset Sum problem asks if a subset adds up to a given target t modulo a given integer m. This is a natural generalization of the Subset Sum problem (where m = + [infinity symbol]) with ties to additive combinatorics and cryptography. The non-modular case was …
-
On subset-sum-distinct sequences of positive integers
"An SSD-sequence of integers is one in which each subset is uniquely determined by its sum. Such sequences are ""sparse"". Ryavec used a generating function technique to show that the sum of the reciprocals of the terms of such a sequence is at most two, and that the greedy algorithm generates the …
-
Subset sum and community problems: From social to geometry
… positive integers and a target integer $u$, the subset sum problem is to decide if there is a subset of $S$ that sums up to $u$. We present a series of new algorithms that compute and return \emph{all} the realizable subset sums up to the integer $u$ in …
-
Applications Of The Subset Sum Problem Over Finite Abelian Groups
… $f:D\rightarrow G$, we find the number of $r$-subsets $S\subseteq D$ where for $b\in G$, \begin{align*} \sum_{x\in S}f(x)=b. \end{align*} We obtain simple exact expressions when $f$ is an abelian group homomorphism. When $G=\Fq$, we extend known results when $D\in\{\Fq,\Fq^*\}$ and $f(x)=x^N$, …
-
Formal verification of biologically inspired computing models
… These are: ΠSSP - a cP system that solves the subset sum problem in linear time, and Π Sudoku - a cP system that solves Sudoku (m * m) in sublinear time. In order to automate the verification process, we proposed several mapping guidelines, which can be used to transform cP system notation into …
-
Evolutionary combinatorial optimisation for energy storage scheduling, and web-based power systems analysis using PHP
… the one-dimensional bin packing problem and the subset sum problem and solves them heuristically with specific modifications and transformations to obtain viable schedules. The schedules may then be optimised further using genetic algorithm optimisation. Comparative analyses with other algorithms …
-
Optimization of Test and Design-for-Testability Solutions for Many-Core System-on-Chip Designs
… is used as a TAM. First, an algorithm based on subset-sum formulation to solve the test-delivery problem in NOCs with arbitrary topology is presented. For the important class of NOCs with a grid topology, the optimization problem is modeled as an NOC partitioning problem and solved using dynamic …
-
Programación celular resolución eficiente de problemas numéricos NP-completos
… de tres problemas numéricos NP-completos: Subset Sum, Knapsack y Partición, a través de sistemas celulares reconocedores con membranas activas. En todas las soluciones se sigue una misma estructura: - En primer lugar, se presentan los diseños de las correspondientes familias de sistemas …