Approximation Algorithms for Packing and Independent Set Problems

• Grant number: 23/13972-2
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: December 01, 2023
• End date: November 30, 2024
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Flávio Keidi Miyazawa
• Grantee: Gabriel Medrano Silva
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated research grant: 22/05803-3 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings, AP.TEM

Abstract

Combinatorial optimization problems are the subject of extensive study due to their numerous practical applications. Among the methods used to address such problems, approximation algorithms are one of the primary tools, owing to their speed compared to other approaches. This project explores the key techniques of this paradigm, focusing on two classic problems that have a substantial body of literature: the geometric packing problem and the geometric independent set problem.