2 citations · 3 across the 4 of their papers we have counts for
4 papers · 1 filter
Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
Parinya Chalermsook, Matthias Kaul, Matthias Mnich +3
The fundamental sparsest cut problem takes as input a graph together with the edge costs and demands, and seeks a cut that minimizes the ratio between the costs and demands acr…
PTAS for Steiner Tree on Map Graphs
Jarosław Byrka, Mateusz Lewandowski, Syed Mohammad Meesum +2
We study the Steiner tree problem on map graphs, which substantially generalize planar graphs as they allow arbitrarily large cliques. We obtain a PTAS for Steiner tree on map grap…
A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints
Eyal Mizrachi, Roy Schwartz, Joachim Spoerhase +1
Motivated by applications in machine learning, such as subset selection and data summarization, we consider the problem of maximizing a monotone submodular function subject to mixe…
An approximation algorithm for Uniform Capacitated k-Median problem with 1 + ε capacity violation
Jarosław Byrka, Bartosz Rybicki, Sumedha Uniyal
We study the Capacitated k-Median problem, for which all the known constant factor approximation algorithms violate either the number of facilities or the capacities. While the sta…