Penerapan Struktur K-dimensional Tree pada Penyelesaian Dominasi Pareto

Suryono, Thomas Juan Mahardika (2025) Penerapan Struktur K-dimensional Tree pada Penyelesaian Dominasi Pareto. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025211016-Undergraduate_Thesis.pdf - Accepted Version Download (3MB)

Abstract

Eolymp merupakan situs penilaian kode daring yang berasal dari Ukraina. Eolymp memiliki berbagai soal dengan berbagai tingkat kesulitan yang dapat diselesaikan pengguna dengan menggunakan kode. Studi kasus yang digunakan pada tugas akhir ini terdapat pada Eolymp kode soal 100 berjudul “Pareto Domination” yang memiliki tautan https://basecamp.eolymp.com/en/problems/100.
Sebuah titik dengan koordinat (x0, x1, …, xM-1) dikatakan didominasi oleh sebuah titik dengan koordinat (y0, y1, …, yM-1) jika xi ≤ yi untuk setiap i (0 ≤ i ≤ M-1), dengan M merupakan dimensi. Konsep dominasi ini sama seperti dominasi Pareto. Diberikan himpunan titik. Titik x merupakan titik tidak didominasi jika titik x tidak didominasi oleh titik lain manapun dalam himpunan. Tujuan dari studi kasus ini adalah menemukan banyak titik tidak didominasi dari himpunan titik yang diberikan.
Persoalan dominasi Pareto termasuk kasus NP-hard karena perlu mereduksi kompleksitas kuadratik agar dapat memenuhi batasan waktu eksekusi, yakni 10 detik. Solusi menggunakan penerapan k-d tree (k-dimensional tree) yang dikombinasikan dengan teknik bounding box dan pendekatan dua fase.
Berdasarkan hasil uji coba, solusi penerapan k-d tree mampu menyelesaikan persoalan dalam waktu 326 milidetik hingga 329 milidetik dengan penggunaan memori antara 4,15 MB dan 4,16 MB pada 22 September 2024.
==============================================================================================================================
Eolymp is an online code judge site originating from Ukraine. Eolymp offers a variety of problems with different levels of difficulty that users can solve using code. The case study used in this final project is found on the Eolymp under problem code 100, titled “Pareto Domination”, with the link: https://basecamp.eolymp.com/en/problems/100.
A point with coordinates (x₀, x₁, …, xₘ₋₁) is said to be dominated by a point with coordinates (y₀, y₁, …, yₘ₋₁) if xᵢ ≤ yᵢ for every i (0 ≤ i ≤ M-1), where M represents the number of dimensions. This concept of domination is the same as Pareto domination. Given a set of points, a point x is considered a non-dominated point if it is not dominated by any other point in the set. The goal of this case study is to determine the number of non-dominated points in the given set of points.
The Pareto domination problem is NP-hard because it requires reducing quadratic complexity to meet the execution time limit of 10 seconds. The solution involves applicating k-d tree (k-dimensional tree) combined with the bounding box technique and two-phase approach.
Based on test results, the k-d tree application was able to solve the problem in 326 milliseconds to 329 milliseconds, with memory usage ranging from 4,15 MB to 4.16 MB, as of September 22, 2024.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Dominasi Pareto, K-dimensional Tree, Pendekatan Dua Fase, Pareto Domination, K-dimensional Tree, Two Phase Approach
Subjects:	Q Science > QA Mathematics > QA76.F56 Data structures (Computer science) Q Science > QA Mathematics > QA9.58 Algorithms
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Thomas Juan Mahardika Suryono
Date Deposited:	01 Feb 2025 07:30
Last Modified:	01 Feb 2025 07:30
URI:	http://repository.its.ac.id/id/eprint/117438

Actions (login required)

View Item