3 citations · 5 across the 7 of their papers we have counts for
8 papers · 1 filter
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…
Node Connectivity Augmentation via Iterative Randomized Rounding
Haris Angelidakis, Dylan Hyatt-Denesik, Laura Sanità
Many network design problems deal with the design of low-cost networks that are resilient to the failure of their elements, such as nodes or links. One such problem is Connectivity…
Simpler and Stronger Approaches for Non-Uniform Hypergraph Matching and the Füredi, Kahn, and Seymour Conjecture
Georg Anegg, Haris Angelidakis, Rico Zenklusen
A well-known conjecture of Füredi, Kahn, and Seymour (1993) on non-uniform hypergraph matching states that for any hypergraph with edge weights , there exists a matching suc…
A Technique for Obtaining True Approximations for -Center with Covering Constraints
Georg Anegg, Haris Angelidakis, Adam Kurpisz +1
There has been a recent surge of interest in incorporating fairness aspects into classical clustering problems. Two recently introduced variants of the -Center problem in this s…
Bilu-Linial stability, certified algorithms and the Independent Set problem
Haris Angelidakis, Pranjal Awasthi, Avrim Blum +2
We study the Maximum Independent Set (MIS) problem under the notion of stability introduced by Bilu and Linial (2010): a weighted instance of MIS is -stable if it has a unique o…
Shortest path queries, graph partitioning and covering problems in worst and beyond worst case settings
Haris Angelidakis
In this thesis, we design algorithms for several NP-hard problems in both worst and beyond worst case settings. In the first part of the thesis, we apply the traditional worst case…
Algorithmic and Hardness Results for the Hub Labeling Problem
Haris Angelidakis, Yury Makarychev, Vsevolod Oparin
There has been significant success in designing highly efficient algorithms for distance and shortest-path queries in recent years; many of the state-of-the-art algorithms use the…
An Improved Integrality Gap for the Calinescu-Karloff-Rabani Relaxation for Multiway Cut
Haris Angelidakis, Yury Makarychev, Pasin Manurangsi
We construct an improved integrality gap instance for the Calinescu-Karloff-Rabani LP relaxation of the Multiway Cut problem. In particular, for terminals, our inst…