1 citations · 1 across the 4 of their papers we have counts for
4 papers · 1 filter
Dense Steiner problems: Approximation algorithms and inapproximability
Marek Karpinski, Mateusz Lewandowski, Syed Mohammad Meesum +1
The Steiner Tree problem is a classical problem in combinatorial optimization: the goal is to connect a set of terminals in a graph by a tree of minimum size. Karpinski and…
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…
Constant factor FPT approximation for capacitated k-median
Marek Adamczyk, Jarosław Byrka, Jan Marcinkowski +2
Capacitated k-median is one of the few outstanding optimization problems for which the existence of a polynomial time constant factor approximation algorithm remains an open proble…
Rank Vertex Cover as a Natural Problem for Algebraic Compression
Syed Mohammad Meesum, Fahad Panolan, Saket Saurabh +1
The question of the existence of a polynomial kernelization of the Vertex Cover Above LP problem has been a longstanding, notorious open problem in Parameterized Complexity. Five y…