9 papers
Graph Partitioning with Demands: Generalized Conductance and its Applications
Michał Szyfelbein, Dariusz Dereniowski
We study various graph partitioning tasks subject to general demands. In Graph Partitioning with Demands (GPD), the goal is to delete minimum cost supply edge set so that each rema…
Hierarchical -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 b…
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…
Simpler Logarithmic Approximation Algorithms for the Optimal Decision Tree and Adaptive Set Cover
Michał Szyfelbein
We study the problem of constructing a decision tree that identifies an unknown hypothesis from a given ground set, under both average- and worst-case cost. The Optimal Decision Tr…
Min-Sum Set Cover on Parallel Machines
Michał Szyfelbein
We consider a generalization of the Min-Sum Set Cover to the setup with set-sequences, or in scheduling terminology, parallel machines. We call this problem Parallel Min-Su…
Average Case Graph Searching in Non-Uniform Cost Models
Michał Szyfelbein
We consider the following generalization of the classic Binary Search Problem: a searcher is required to find a hidden target vertex in a graph , by iteratively performing q…
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.…
Approximating the Average-Case Graph Search Problem with Non-Uniform Costs
Michał Szyfelbein
Consider the following generalization of the classic binary search problem: A searcher is required to find a hidden target vertex in a graph . To do so, they iteratively per…
Searching in trees with -up-modular cost functions
Michał Szyfelbein
Consider the following generalization of the classic binary search problem: a searcher is required to find a hidden vertex in a tree . To do so, they iteratively perform que…