Dariusz Dereniowski

2 papers indexed

arxivcs.DScs.LG2026-07-14

Graph Partitioning with Demands: Generalized Conductance and its Applications

In this work, we study various graph partitioning problems under a general demand model. In each such task, we are given a graph $G=(V,E,c,w)$ with a capacity function $c\colon E\to \mathbb{N}$ and a demand function $w\colon V\times V\to \mathbb{N}$. Our main focus is the problem…

View free PDFSource page

arxivcs.DScs.LG2026-07-14

Hierarchical $\mathcal{F}$-Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs

Michał Szyfelbein, Dariusz Dereniowski

Consider the following variation on the Hierarchical Clustering problem: Usually, while building a hierarchical clustering, one recursively partitions the data until each cluster becomes a singleton. We relax the halting condition of the recursive process to stop whenever the rem…

View free PDFSource page