From the 2 of 5 linked papers with an AI index.
5 papers
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.…
A framework for distributed discrete evacuation strategies
Piotr Borowiecki, Dariusz Dereniowski, Åukasz Kuszner
In this paper, we study discrete evacuation in networks, where agents know the network topology and designated exit nodes but do not know the number and initial positions of other…
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…