Partition Problem

Batakliev, Emil (author), Robič, Borut (mentor)

In this thesis we will focus on different algorithms for solving the Partition Problem. First, we will explain what the Partition Problem is and why it has been causing so many difficulties even in its simplest form. Then we will focus on different methods and algorithms for solving this problem that were published in the last few decades. We will explain their underlying ideas, positive and negative properties, asymptotic time complexities, and their actual speed. We will also present an algorithm that is based on our own ideas. All the algorithms will be experimentally evaluated on a set of problem instances. The goal of this work is not to find the best algorithm for the problem of partitioning, but rather to explain various algorithms for solving it, emphasize their positive and negative sides, thus allowing the user to pick the most appropriate algorithm for the scenario/problem instance at hand.

• Language: English
• Keywords: subarray, algorithm, complexity
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2020
• PID: 20.500.12556/RUL-119213
• COBISS.SI-ID: 27794179
• Publication date in RUL: 04.09.2020

Secondary language

• Language: Slovenian
• Title: Problem razdelitve

Abstract

V delu se bomo osredotočili na razne algoritme za rešavanje Problema Razdelitve. Najprej bomo pojasili, kaj je problem razdelitve in zakaj je v preteklosti povzročil - celo v svoji najenostavnejši različici - toliko preglavic. Nato se bomo posvetili raznim metodam in algoritmom za rešavanje tega problema, ki so bili objavljeni v zadnjem desetletju. Razložili bomo njihove zamisli, prednosti in slabosti, njihove asimptotične časovne zahtevnosti in dejanske hitrosti. Predstavili bomo tudi algoritem, ki smo ga zasnovali sami. Vse algoritme bomo eksperimentalno ovrednotili, na množici primerov problema. Cilj našega dela ni poiskati najboljši algoritem za problem razdelitve, pač pa razložiti delovanje takšnih algoritmov, izpostaviti njihove prednosti in slabosti, in tako omogočiti uporabniku, da izbere tistega, ki je za rešitev njegove situacije/primera problema, najprimernejši.

• Keywords: podtabela, algoritem, zahtevnost