dr hab. Bartłomiej Bosek​
​​​​​​​

czwartek 14:00-15:30, sala 0174

Jest to seminarium magisterskie, którego tematyka dotyczy optymalizacji kombinatorycznej. W szczególności interesują nas następujące tematy:

1. Zaawansowane algorytmy znajdujące skojarzenia w grafach (także dwudzielnych) w przypadkach nieważonych i ważonych krawędzi.
2. Problemy konstruowania on-line skojarzeń w grafach dwudzielnych, AdWords Problem - rozwiązania optymalne, randomizowane.
3. Algorytmiczne aspekty pokrycia uniłańcuchami produktów częściowych porządków.

Strona seminarium na UsosWeb znajduje się tutaj.

Hubert Bernacki

The nearest neighbor search problem asks how to preprocess a set S of n points in ℝ^d, under a given Minkowski metric, to answer the following query: given a point q, find its closest point in S. This problem arises naturally in many branches of computer science, including machine learning, bioinformatics, and computational geometry. Before Arya et al. published “An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions”, much of the focus was on exact search with O(log n) query time and O(n) auxiliary space, but achieving these bounds proved difficult.

The authors considered an approximate version, where the goal is to find a point in S whose distance from q is at most (1 + ε) times the distance to its nearest neighbor. For fixed dimension d and fixed ε > 0, they achieve O(n) space and O(log n) query time. In this presentation, we will look at the BBD-trees that achieve these results.

1. S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, A. Y. Wu. An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions (1998).
2. Hubert Bernacki. An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions. slides. (2026).