Dynamic and probabilistic models in optimization : algorithms for combinatorial problems with applications in machine learning

Abstract

Combinatorial optimization problems have gained significant attention in recent years due to their wide-ranging applications across various domains, including machine learning. Efficient solutions to these problems play a crucial role in advancing areas such as data analysis, pattern recognition, and more. However, the dynamic and probabilistic nature of real-world scenarios poses unique challenges, such as time dependency, computational complexity, and adaptability, that require novel algorithmic approaches. This thesis explores three fundamental combinatorial problems in machine learning under dynamic and probabilistic models. The objective is to develop efficient algorithms that adapt to changing environments and incorporate probabilistic factors for enhanced performance.

For the fully dynamic $k$-center clustering with outliers problem, the first constant bi-criteria approximation algorithm is proposed. Experimental analysis demonstrates its effectiveness, including integration as a subroutine for dimension reduction in a price prediction problem. The fully dynamic Euclidean Steiner tree problem is addressed with an algorithm that maintains a $(1+\epsilon)$-approximate solution using tree traversal queries, even with point insertions and deletions with amortized update and query time polynomial in the number of points. In the generalized sorting with predictions problem, a novel Monte Carlo approach is introduced, improving the number of probes required to find a Hamiltonian path in a directed acyclic graph in the only known result from $O(n\log n+w)$ to $O(n\log w+w)$.