2 citations · 3 across the 4 of their papers we have counts for
6 papers
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…
Multi-transversals for Triangles and the Tuza's Conjecture
Parinya Chalermsook, Samir Khuller, Pattara Sukprasert +1
In this paper, we study a primal and dual relationship about triangles: For any graph , let be the maximum number of edge-disjoint triangles in , and be the min…
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…
A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs
Parinya Chalermsook, Andreas Schmid, Sumedha Uniyal
A cactus graph is a graph in which any two cycles are edge-disjoint. We present a constructive proof of the fact that any plane graph contains a cactus subgraph where c…
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…