University of Twente Student Theses
Balanced Matching Algorithms Against an Adversary on the Line
Olink, Colin (2025) Balanced Matching Algorithms Against an Adversary on the Line.
|
PDF
1MB |
| Abstract: | Recently, it was shown that Online Matching on the Line algorithms are Ω(√log n)- competitive against an oblivious adversary. In the proof, a particular hard place- ment of requests and servers on the line was considered which we used as an adversary against two balancing algorithms. These algorithms are referred to as the Middle Matching Algorithm (MMA) and Balanced Matching Algorithm (BMA), and they aim to be Θ(√log n)-competitive against the adversary. For the MMA we were able to prove that it is O(n)-competitive against the adversary, while we had experimental findings that suggest that it may be Θ(√log n)-competitive. Regarding the BMA, we lack conclusive evidence about the asymptotic behavior of its competitive ratio, as the maximum costs incurred by the BMA have not yet been determined. |
| Item Type: | Essay (Bachelor) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 31 mathematics |
| Programme: | Applied Mathematics BSc (56965) |
| Link to this item: | https://purl.utwente.nl/essays/105207 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page