1 citations · 1 across the 2 of their papers we have counts for
6 papers
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…
Hypergraphic Degree Sequences are Hard
Antoine Deza, Asaf Levin, Syed M. Meesum +1
We show that deciding if a given vector is the degree sequence of a 3-hypergraph is NP-complete.
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…
Approximate Shifted Combinatorial Optimization
Martin Koutecky, Asaf Levin, Syed M. Meesum +1
Shifted combinatorial optimization is a new nonlinear optimization framework, which is a broad extension of standard combinatorial optimization, involving the choice of several fea…
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…