Online Maximum Independent Set and Independent Kissing Number

Thumbnail Image

Files

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Bachelor's thesis
Electronic archive copy is available locally at the Harald Herlin Learning Centre. The staff of Aalto University has access to the electronic bachelor's theses by logging into Aaltodoc with their personal Aalto user ID. Read more about the availability of the bachelor's theses.
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2025-09-04

Department

Major/Subject

Tietotekniikka

Mcode

SCI3027

Degree programme

Teknistieteellinen kandidaattiohjelma

Language

en

Pages

23

Series

Abstract

This thesis reproduces results for the performance of online algorithms for the maximum independent set problem on intersection graphs. The greedy algorithm is proven to be optimal with a competitive ratio of $\zeta$, where $\zeta$ is the independent kissing number of the graph. For any given graph $G$, the value of independent kissing number $\zeta$ equals ``the size of the largest induced star in $G$'' $-1$. Therefore, the value of $\zeta$ for different types of objects become crucial and interesting to investigate. In this thesis, we present a combination of some already known as well as some new bounds for the values of the independent kissing $\zeta$. The bounds on $\zeta$ for the new results are as follows. For hypercubes in $\mathbb{R}^d$ with side lengths in the range $[1,m]$. We prove a common lower bound of $(\lceil m\rceil+1)^d$ for both axis-aligned and arbitrarily oriented hypercubes. For axis-aligned hypercubes in $\mathbb{R}^d$ we prove a new upper bound of $(\lfloor m\rfloor+2)^d$, and for arbitrarily oriented hypercubes in $\mathbb{R}^d$, we prove a new upper bound of $\sum_{j=0}^d\binom{d}{j}\kappa_jm^{d-j}(\sqrt{d})^{j}$, where $\kappa_j$ is the volume of a $j$-dimensional unit radius ball.

Tämä opinnäytetyö käsittelee online-algoritmin suorituskykyä suurimman itsenäisen joukon (engl. independent set) etsinnässä geometrisistä leikkausgraafeista (engl. intersection graph). Ahneen algoritmin osoitetaan olevan optimaalinen $\zeta$:n kilpailusuhteella (engl. competitive ratio), missä $\zeta$ on verkon itsenäinen kosketusluku (engl. independent kissing number). Graafille $G$ itsenäinen kosketusluku $\zeta$ vastaa ``suurimman graafissa indusoidun tähden kokoa'' $-1$. Tämän seurauksena $\zeta$ on keskeinen tutkimuksen kohde eri kappaleperheille. Tässä opinnäytetyössä esitellään jo tunnettuja sekä uusia rajoja itsenäiselle kosketusluvulle eri kappaleperheissä. Uudet rajat koskevat $d$-ulotteisia hyperkuutioita, joiden sivujen pituudet ovat välillä $[1,m]$. Akselien suuntaisille hyperkuutioille alarajaksi osoitetaan $(\lceil m\rceil + 1)^d$, ja ylärajaksi $(\lfloor m\rfloor+2)^d$, missä $m\in\mathbb{R}$ ja $m\geq1$. Mielivaltaisesti suunnatuille hyperkuutioille edellinen alaraja toimii alarajana. Osoitamme uuden ylärajan $\sum_{j=0}^d\binom{d}{j}\kappa_jm^{d-j}(\sqrt{d})^{j}$, missä $\kappa_j$ on $j$-ulotteisen yksikkösäteisen pallon tilavuu

Description

Supervisor

Savioja, Lauri

Thesis advisor

Singh, Satyam

Keywords

graph theory, independent set, online algorithm, intersection graph, independent kissing number

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202510218398

Collections

[kand] Perustieteiden korkeakoulu / SCI