From the 2 of 7 linked papers with an AI index.
6 papers · 1 filter
Graph Partitioning with Demands: Generalized Conductance and its Applications
MichaÅ Szyfelbein, Dariusz Dereniowski
The paper studies graph partitioning problems with vertex demand functions and introduces the generalized conductance measure, providing O(log n) approximation algorithms via reduc…
Hierarchical -Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs
MichaÅ Szyfelbein, Dariusz Dereniowski
The paper studies hierarchical clustering where the recursion stops once clusters belong to a specified graph class (trees or bounded‑diameter graphs), providing poly‑time logarith…
Precedence-Constrained Decision Trees and Coverings
MichaÅ Szyfelbein, Dariusz Dereniowski
This work considers a number of optimization problems and reductive relations between them. The two main problems we are interested in are the Optimal Decision Tree and Set Cover.…
Noisy (Binary) Searching: Simple, Fast and Correct
Dariusz Dereniowski, Aleksander Åukasiewicz, PrzemysÅaw UznaÅski
This work considers the problem of the noisy binary search in a sorted array. The noise is modeled by a parameter that dictates that a comparison can be incorrect with probabil…
Low-degree spanning trees of -edge-connected graphs in linear time
Dariusz Dereniowski, Janusz DybizbaÅski, PrzemysÅaw KarpiÅski +2
We present a simple linear-time algorithm that finds a spanning tree of a given -edge-connected graph such that each vertex of has degree at most $\lceil \frac{Â…
On multidimensional generalization of binary search
Dariusz Dereniowski, PrzemysÅaw Gordinowicz, Karolina Wróbel
This work generalizes the binary search problem to a -dimensional domain , where and , in the following way. Giv…