3 papers
cs.DS2024
On contention resolution for the hypergraph matching, knapsack, and -column sparse packing problems
Ivan Sergeev
The contention resolution framework is a versatile rounding technique used as a part of the relaxation and rounding approach for solving constrained submodular function maximizatio…
cs.DS2023
Constant-Competitiveness for Random Assignment Matroid Secretary Without Knowing the Matroid
Richard Santiago, Ivan Sergeev, Rico Zenklusen
The Matroid Secretary Conjecture is a notorious open problem in online optimization. It claims the existence of an -competitive algorithm for the Matroid Secretary Problem (M…
cs.DS2021
Improved approximation algorithms for two Euclidean k-Center variants
Haris Angelidakis, Ivan Sergeev, Pontus Westermark
The -Center problem is one of the most popular clustering problems. After decades of work, the complexity of most of its variants on general metrics is now well understood. Surp…