From the 2 of 9 linked papers with an AI index.
9 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…
Polylogarithmic Approximation for Covering and Connecting Multi-Interface Networks
MichaÅ Szyfelbein, Camille Richer
We study problems related to connecting multi-interface networks of wireless devices. These problems can be modeled using graphs, where vertices represent the devices and edges rep…
Min-Sum Set Cover on Parallel Machines
MichaÅ Szyfelbein
Consider the classical Min-Sum Set Cover problem: We are given a universe of elements and a collection of subsets of . The goal is…
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.…
Simpler Logarithmic Approximation Algorithms for the Optimal Decision Tree and Adaptive Set Cover
MichaÅ Szyfelbein, Michał Szyfelbein
We study a well-known task of constructing a decision tree identifying an unknown hypothesis from a given ground set of hypotheses under both the average- and worst-case cost. The…