Perancangan dan Analisis Penerapan Algoritma Approximation pada Persoalan Non-Polynomial : Studi Kasus SPOJ 32028 Adaparti – Ada And Parties

Janitra, Calvin (2025) Perancangan dan Analisis Penerapan Algoritma Approximation pada Persoalan Non-Polynomial : Studi Kasus SPOJ 32028 Adaparti – Ada And Parties. Project Report. [s.n], [s.l.]. (Unpublished)

Text 5025211020_Project-Report.pdf - Accepted Version Restricted to Repository staff only Download (1MB) | Request a copy

Abstract

Dalam penelitian ini, kami merancang, mengimplementasikan, dan menganalisis penerapan Algoritma Approximation untuk menyelesaikan persoalan Non-Polynomial (NP-Hard), dengan studi kasus dari SPOJ 32028 ADAPARTI – Ada and Parties. Masalah ini melibatkan pembentukan kelompok teman di mana setiap teman harus berada dalam kelompok yang sama dengan semua temannya tanpa ada musuh dalam kelompok tersebut, serta meminimalkan jumlah perubahan hubungan (baik penambahan maupun penghapusan hubungan). Beberapa pendekatan dapat digunakan untuk menyelesaikan permasalahan ini yaitu Algoritma Pivoting, Algoritma Branch and Bound, dan Kernel. Setelah itu, perlu adanya optimisasi untuk memperbaiki agar solusi yang dihasilkan optimal. Hasil penelitian menunjukkan bahwa pendekatan ini dapat menyelesaikan permasalahan non-polynomial pada studi kasus SPOJ ADAPARTI – Ada and Parties secara efisien, mencapai pembentukan kelompok yang diinginkan dengan operasi minimal.
=================================================================================================================================
In this research, we design, implement, and analyze the application of an Approximation Algorithm to solve a Non-Polynomial (NP-Hard) problem, using the case study from SPOJ 32028 ADAPARTI – Ada and Parties. This problem involves forming groups of friends where each friend must be in the same group as all of their friends without having enemies in the same group, while minimizing the number of relationship modifications (either additions or removals). Several approaches can be used to tackle this problem, including the Pivoting Algorithm, the Branch and Bound Algorithm, and the Kernel. Afterwards, optimization is needed to improve the solution so that it is optimal. The results show that this approach can efficiently solve the non-polynomial problem in the SPOJ ADAPARTI – Ada and Parties case study, successfully creating the desired groups with minimal operations.

Item Type:	Monograph (Project Report)
Uncontrolled Keywords:	Kata Kunci : np-hard, clustering, approximation ======================================================================================================================== Keywords: np-hard, clustering, approximation
Subjects:	T Technology > T Technology (General) > T58.62 Decision support systems
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Calvin Janitra
Date Deposited:	26 Jun 2025 08:03
Last Modified:	26 Jun 2025 08:03
URI:	http://repository.its.ac.id/id/eprint/119267

Actions (login required)

View Item