1 citations · 1 across the 4 of their papers we have counts for
9 papers
Rectangle Tiling Binary Arrays
Pratik Ghosal, Syed Mohammad Meesum, Katarzyna Paluch
The problem of rectangle tiling binary arrays is defined as follows. Given an array of zeros and ones and a natural number , our task is to partition into a…
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…
Optimization over Degree Sequences
Antoine Deza, Asaf Levin, Syed M. Meesum +1
We introduce and study the problem of optimizing arbitrary functions over degree sequences of hypergraphs and multihypergraphs. We show that over multihypergraphs the problem can b…
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…
Cyclic Hypergraph Degree Sequences
Syed Mohammad Meesum
The problem of efficiently characterizing degree sequences of simple hypergraphs is a fundamental long-standing open problem in Graph Theory. Several results are known for restrict…